Say what you will, but T-Mobile has been an outstanding company - I've used them for 5+ years and I can't tell you the discounts, offers, late fees, other misc things they've taken care of. You get a sense they really value their customers, and especially value a long patronage with them.
I will be sticking with T-Mobile, as they just feel less evil than other cell phone companies.
In fact, even if I really wanted an iphone, I refuse to go at&t, I pay $50 less for unlimited nationwide calling, have 3G and a G1, close enough.
You could install sip droid on an unlocked android like the adp1 (or install unknown sources on a carrier phone) or go with any number of sip clients for pdas. Then you still need to provision a line for the other end of the sip connection, but you'll have a pda that can make calls.
except google, apparently.