Mobil si kup jaký chceš - může to být Lumia nebo cokoli s Androidem (předpoklad je jen, že to má verzi 4.1 a vyšší), následně nainstaluj Mapy Here (bývalé Nokia maps). Pro Android jsou sice ještě "beta", ale fungují velmi dobře. Mapové podklady jsou zdarma a s OSM nesrovnatelné (lepší), stažení probíhá přímo v navigaci.

https://play.google.com/store/apps/details?id=com. here.app.maps

http://www.svetandroida.cz/mapy-nokia-here-dostupn ost-201410