Google krankt daran, eine de facto Online-Navigation zu sein, d.h. wenn du im Ausland bist und keine teuren Roaming-Gebühren zahlen willst - adieu Navigation.
Wenn du mal im Funkloch bist - adieu Navigation.
Ich habe mich vor ca einem halben Jahr mit dem Thema beschäftigt, da mir mein alter 15€ Plastik-Ebay Navi-Halter bei 80km/h brach und mein Navi auf der Landstraße davonflog. Da war eine neue Lösung fällig;
ich entschied mich, mir nen stabilen Halter zu besorgen (Metal-Kugelgelenk) und daran meine Handy-Autohalterung zu befestigen (habe ein Motorola Atrix mit Cardock)
als Offline-Navi-Lösung (d.h. alle Karten auf Handy gespeichert!) kann ich empfehlen:
Osmand - als Kurzform für OpenStreetMapAndroid
es strotzt vor Einstellmöglichkeiten, bietet dir die ganze Welt zum Download an und hat sehr, sehr, sehr detaillierte Karten. Die taugen auch zur Orientierung im Wald, da selbst kleinste POIs (z.B. Holzhütten im Wald) verzeichnet sind.
Allerdings ist die Menüführung gewöhnungsbedürftigt und die Vielzahl an Infos auch durchaus erstmal erschlagend bzw. verwirrend.
Wenn du weitere Softwarelösungen suchst, anbei eine Übersicht:
http://wiki.openstreetmap.org/wiki/DE:Android
Was ich nicht empfehlen kann (habs für 60€ gekauft) ist Navigon für Android. App stürzt öfters mal ab, jedes Pups-Feature kostet Extra und der Bildschirm wird mit unsinnigen Infos in für mich zu großer Schrift zugemüllt...