Witness the report yesterday that they're not supporting Google Wallet.
Your choice may have more to do with your vendor than with the phone itself.
I got my mom a Samsung Epic 4G about a year ago. Keyboard, Android, can do web stuff, etc. It was on Sprint. It seemed to work pretty well. (Past tense because it seems to have walked off somewhere.) I never tried 4G with it.
http://wireless.amaz...nt/dp/B003ZDO2H6/
Sprint is pretty good in some areas, and did well in the recent Consumer Reports survey, but seems to have the slowest 3G at the moment. Verizon seems to have the best network, but is up to its old tricks. J is on a cheap Verizon plan that doesn't include text messages. She gets frequent SMS spam that she has to pay for because Verizon won't block them. :-/ AT&T is GSM (yay!) but has crap infrastructure and drops calls (boo!). Maybe Virgin or Cricket or some of the other tiny providers are better in some respects, but they piggyback on the big guys' networks, so they can't fix that.
Maybe pick a provider, grab a recent phone off eBay, activate it on your existing plan (you should be able to do so without a new contract, I think), and see how you like it. If you don't like it, rinse and repeat. If you really like it, change your plan to enable the fancy features if necessary.
HTH. Good luck!
Cheers,
Scott.