I have a 770, but I've tried all of this on it running 2007HE, so it ought to be somewhat similar to an N800 in terms of what works and what doesn't....

I am an AT&Tingular customer. I have an 8125 PDA phone. It sort of worked with the 770. By sort of, I mean that I could connect after 3 or 4 tries, and then the data would work for a few hundred KB then die. The 8125 worked perfectly with my laptop and DUN, so it's something in how it communicates with the 770. I then tethered my 770 with my wife's old Motorola V330 with my SIM, and it worked perfectly. Immediate connection, and no weird hiccups, good EDGE speeds. I recently picked up a 2nd Gen Samsung Sync A707 off of eBay specifically for its DUN + 3G capabilities. Works flawlessly with the N770. Connections are immediate, constant, and just about as fast as my home DSL connection when I'm in a good 3G area (500-800kbs). The N770 can even browse the Sync's folders to move files about, grab photos for emailing, etc.

If you go with a AT&T or T-Mobile, look for a quad-band GSM phone with at least EDGE data capability and bluetooth support with the DUN profile. I'd think you would have good luck with any Nokia, especially the N75 since it's the *only* Nokia phone that works with the higher-speed 3G UMTS network in the US. I can vouch for the Samsung Sync. I've heard the Motorola V3xx might be a good candidate, as it supports the blazing fast 3.6mb HSDPA standard for 3.5G once it's deployed. But really, it depends on what you want to do. When I'm away from landline internet, all I care about is checking my email, reading the news, finding the nearest restaurant, or checking the weather. And for that, an EDGE connection (100ish kbs) is satisfactory.

As the other poster mentioned, all of the WM6 and any WM5 with AKU3 (AT&T 8525 and Blackjack are examples) have DUN removed and replaced ith PAN. The 770/800 don't directly support PAN, but there is a script or two floating around here that let you do it, but it's not the 'click, select, bam' connection that you get with DUN. I have seen some threads over on the HTC boards of some folks having pretty good luck in re-instaling DUN on these devices.

The really important thing to understand with cell phone data-packages is which officially allow tethering. WIth AT&T, the only packages that officially support and allow tethering are the $59.99 and up laptop connect plans. To follow the rules, that's what you'll need. That would give you unlimited data on the phone itself, plus the support of AT&T to tether to your N800 or laptop. It is, however, widely known that the 'lesser' data plans do allow you to tether at the same speeds (it's all the same network) for far less money. It is very common to read of folks using the $39.99 PDA Connect and even the $19.99 MediaConnect plans that get by with hundreds of MB/month of tethering to PDA's and laptops with no extra charges, nor cease-and-desist letters from AT&T. The question has been debated for years as to what the limits are, and where AT&T/Cingular will 'cut-you-off', bump you to a different plan, or simply send you a bill for $8,000 worth of data charges. There have recently been some more grumbles over on HowardForums regarding some new auditing by AT&T that may put an end to tethering on unofficial plans. But again, this topic comes up all the time and frequently will have 'AT&T insiders' posting that the end of tethering is at hand yet it never happens. The rule of thumb that I've come to understand from reading hundreds of posts on the subject is that so long as you don't abuse it (multi GB/month, bittorrent downloads, running your own server, etc), you can get by on the lesser plans for occasional tethering. Not a replacement for your home DSL, but those times when you need to check google maps or your email from your PDA/laptop when you're on the go. But even doing that is technically in violation of their terms of service, so do so at your own risk. It's a lot like speeding. You may get by with it for years without getting a ticket, but someday you may get caught and you'll have to pay the price.

FWIW, I used to be a T-Mobile subscriber. I still would be if I could get adequate service at my workplace. Their policy regarding tethering was much clearer than AT&Ts. It simply wouldn't work on the cheap $5-$10 cell phone data plans, but it did work and was permitted on their $30ish PDA and up data plans. Much better than the cloak-and-dagger approach of AT&T.