I don't think getting iPhone would be that big of a deal. If you jail break it, you have access to all of it's underlying UNIX internals

For me, I found the cheapest phone that gave me 3G access (with the ability to receive calls while it's in use) and went with it. In my case, the phone ended up being free because a friend gave it to me, but it runs Windows

I'm using the Samsung Blackjack with AT&Ts $20 unlimited net plan. Newer Windows devices use something called PAN over Bluetooth, which is currently hacked support in to Diablo. In all, it works pretty well for me.

There are also really cheap phones if Edge is enough for you. I have a Nokia 6681 (or 6682? I can't remember the exact number, sorry) -- I couldn't use Edge and talk at the same time, but it's Symbian so I imagine it will tether with the n8x0 easily.