I just bought a HTC TyTN II with Windows Mobile 6. It's really more like a PC than a mobile phone so I don't think I'll SMS anymore; just check my facebook status if you want to know what I'm doing! Anyway, I mostly bought it for the integrated GPS and mapping.
I'm told that Google Maps for Mobile works really well on this device (thanks Kristian) but I won't know until I get the phone because it needs to install a client. I've had a quick look at m.live.com but I don't think it can give audible driving directions. If either of these don't work out, there's always Garmin Mobile XT. I also have a Garmin Nuvi so I'll write another post to compare the mapping and satellite navigation capabilities.
My previous phone was a Samsung BlackJack and I seriously considered upgrading to the BlackJack 2. The new Samsung also runs Windows Mobile 6, includes GPS, a slim and lightweight design, QWERTY keypad and great battery life. However, the proprietary connector for charge and USB is a real pain and without Wi-Fi, the decision to buy the TyTN II was pretty easy.
Now, all I need to complete my nerd disguise is a phone belt-pouch and pocket protector. I'm pretty sure they have those at the Microsoft campus store.