Magellan would be it but requires wifi/3G connection as it uses Google Maps and they don't allow caching... Anything available or expected from ported Android apps? Many thanks.
Mapdroyd is available and it can download maps on an initial connection and then store them for later use. Large variety of maps. But I believe it is ONLY maps. No search or routing although I could be wrong.