I agree with gorcorps - IMO the iPhone implements Google Maps best. Followed by the T-Mobile G1. Followed by the more recent blackberries. Followed by the Symbian based phones from Nokia with large screens such as the N95/N96. Followed by Window's Mobile phones such as the Omnia. And I've spent a bunch of time using the iPhone, the G1, a Nokia N95 and several of the newer blackberries including the Blackberry Curve, and also I've spent 30 minutes or so playing with an Omnia.
Andy, the iPhone is my best recommendation, but since you seem to not like that, I'd recommend looking at a T-Mobile G1. Next, take a look at a Blackberry Bold, followed by the Curve 8310. Next, if your definition of cheap goes as high as $300, look at a Nokia N95.
YAY no picture messaging, locked down hardware, Apple not allowing great potential apps just to make them themselves to make money, supporting the worst Monopoly we have seen in a long time. Great way to go.
There are plenty of reasons not to buy an iPhone you mentioned a lot of them zerocool. I don't disagree with them - well, except the monopoly one. But it's worth mentioning that hacking your iPhone resolves a bunch of these - and some statistics estimate that as many as 40% of all iPhone 2G's have been hacked so it's not like this is a really rare procedure done by a few people.
You can add in picture messaging using SwirlyMMS or Flutter for iPhones. Flutter is free, but not all that great. Swirly rocks, but requires a hacked iPhone and isn't free.
http://www.appleiphoneapps.com...utter-real-iphone-mms/
You can unlock both 3G and 2G iPhones - there are several GUI driven applications to choose from and the risk of an issue that kills your phone is pretty much nil in the case of 2G phones, but a bit riskier with 3G iPhones. Or you can buy a SIM adapter for about $20 on Ebay.
If you hack/jailbreak your phone, you can choose any app you want to install.
The worst monopoly we've seen in a long time? Worse than the oligarchy of the oil industry - and yet we all fill up our cars with gasoline or diesel? Worse than the diamond cartel - and yet nearly all married guys have bought diamonds? Apple has a 57% marketshare of music downloads and no marketshare at all in subscription music services (from 2008 data). In the computer business, Apple with 9% market share is more of a monopoly than Microsoft with 88% (
http://www.tuaw.com/2009/01/02...west-since-tracking/)? How exactly is Apple the worst monopoly in a long time? I can think of vastly worse monopolies than Apple that exist today - ones that actually have made the world a worse place by their very existence.