Já osobně bych doporučil Nokiácké Here.

Zatím jsou dostupné pouze v mobilech značky Nokia (což není na závadu) - krabicoidní navigace jsou na ústupu.
Aktualizace map jsou doživotně zdarma (tj. cca 3-4 roky minimálně, polde životnosti telefonu)
Aplikace je chytrá a hlavně rychlá, není to tragedie typu androidích aplikací (sygic a spol.)
Navigace je podporována aplikací pro web (tam si můžeš hledat body zájmu, plánovat cesty apod. a následně sychronizovat do svého mobilu) viz www.here.com (co vidíš tam, vidíš i v mobilu).

Postupně začíná podporovat v ČR i hromadnou dopravu a dopravní info.

edit: pokud ti stačí čr+sr, tak Nokia L520 za nějaké 3 litry. (do budoucna se mají licence měnit a i L520 by měla dostat celsvětovou navigaci AFAIK)