I am desperately in need of a new phone. My trusty Nokia 6600 has served me well, and still continues to chug along, but is plagued by bad sound, connection, small memory, and slow processor. I'm still drooling over the new Nokia N95, but not sure when I can actually get my hands on one (or afford it).
However, there is another drool-worthy phone coming out in January. On the same vein as the Nokia N770 tablet, which is very hackable, the OpenMoko phone is a fully hackable mobile phone. GPS, quad-band GSM/GPRS, SyncML, microSD cards, apt-get install, Linux, GTK goodness. Future versions are expected with WiFi and Bluetooth. via Koen's Blog
Also check out the LinuxDevices article which sports images including mapping applications.