I live ini Manhattan and I have a Nokia N75 which has UMTS speed and then the $20 a month ATT media max plan. Technically you are not supposed to tether but I have been tethering for over two years and never had an issue. I don't stream too much music but I definately have used IM etc. Skype I have used on it before and its passable but the latency is bad. The benefit is you also get a Symbian smartphone phone which for all intents and purposes can cover any shortcomings the N800 has as per PIM software or whatever else. I find the combination to be great. I have heard of others using T-mobile and getting a $6 a month unlimited Edge plan which you can tether with.

There are other good alternatives such as the Sync musicphone which I believe has HSDPA high speed internet and is free on contract and if you really want to splurge but counter the cost by going off contract you can purchase the $650 Nokia N95-3 (US version) which has HSDPA and then just get the media max plan from ATT ($20) .