or, how about just a used contract-free smartphone? This is the route I've been taking, going from an iphone 3G to hopefully soon a nexus one.

Disclaimer: I can't stand carrying both a phone and a pda device in my pocket.