Google just released [Google Maps for the Treo](http://www.google.com/gmm/treo). It is a Palm application which downloads the map over the Internet. It has a simple and usable interface that can use the scroll pad and keyboard for most operations. It can search for addresses and display driving directions. It can also show satellite view and traffic info for major highways.
The lag of downloading the maps can be a little annoying when scrolling to new areas. And since it uses the images, the space and time is larger. Zooming in and out seems to download new images. It requires Internet access so it won’t work outside of cell phone range. I have been having with [Mapopolis](http://www.mapopolis.com) which keeps crashing on me and isn’t usable with the keyboard. But it can work offline with maps and addresses stored on the card. And it GPS which can show the current position and do dynamic directions. A mixture of the two which worked smoothly, downloaded maps as needed, and showed your current position would be perfect.