I tried 3 carriers and here is my experience:
1. T-Mobile - cheapest if you set up your own proxy (5.99/motnth in addition to plan), but is very slow and has very bad coverage if you go outside city limits.
2. Verizon (EVDO). Unless you want to buy expensive data plan, you will use data as plan minutes. I.e. data usage on weekends would be usually free and on regular days every minute you are online counts as a voice calling minute. Coverage is good (same as AT&T in my experience) and it is pretty fast, but not as fast as AT&T 3G.
3. AT&T - very fast (DSL/cable speeds) if you live in 3G area. Decent in EDGE areas. Unlimited data will cost you $20 on top of your plan, coverage is very good.

I do not know about Sprint/Nextel - never tried those.