The best deal in the US (remember, best deal, not best service) is a Sprint SERO plan using the new HTC Mogul cellular phone. You pay $30, you get 500 anytime minutes, unlimited nights and weekends (starting at 7PM) and very, very importantly, UNLIMITED DATA.
But the far more important issue is that the Mogul handles Bluetooth 2.0. This is the stopping block usually. Most phones handle BT 1.2 which will slow you down. The BT 2.0 in the Mogul and in the N800 will allow you to take advantage of the higher EvDO speeds. Additionally, the Mogul will be software upgradable to EvDO Rev. A later in the year. While this will not dramatically improve the download speed, it WILL significantly improve upload speeds and reduce latency, both of which should be a considerable benefit to Skype calling on the N800.