I have been using Alltel's "unlimited" tethering plan. This plan is 25 dollars a month and does NOT require a separate data plan. I am able to use my Motorola razr to tether either my N800 or my laptop. In my area I get around 100 KBps. Not amazingly fast, but bearable.

The only caveat is that I strongly suspect this plan will go away once Verizon completes its take over of Alltel.

Now, it T-Mobile would just complete it's take over of Suncom, I may just switch. We'll see.