FWIW, I currently have Tmobile EDGE with WIFI hotspot use. With my Motorola V330, which is a class 8 EDGE device IIRC, I get consistent 90 to 120 kbps (thats kilobit) using the phone's built in bluetooth. I am grandfathered in my plan at $20/mo. for that. I think it runs $25/mo. now.
I am very tempted to get Sprints EVDO service, which is nice especially since they are currently upgrading to rev. A speeds. $50/mo. for unlimited isn't too bad, and I think I can rationalize that cost since I am dropping my landline at home.