The best value for cingular is the Samsung Sync. Not crazy about the phone (the look especially), but if youre mostly gonna use it for 3G, I say get that. And yes, you can use the $19.99 media plan for tethering with your N800 (except that you need to modify the setting a little bit).

T-Mobile doesn't have 3G (yet)