You might ask why I didn't try NavFree and its USA counterpart. Well, I didn't know about them, because when you search for offline maps you don't find it. Then, for some reason to get maps / routing for the US you need a different version.
Its billed as
"NAVFREE, THE WORLD’S FIRST FREE CROWD-POWERED NAVIGATION SYSTEM!
At first glance its pretty good. For the non-USA version you can download maps after pressing on 'upgrades'. Not 100% intuitive, does the job.
For v1.x of this app, it needs a data connection to look up addresses, so this is not 100% solution to data-less offline navigation. Seems that v2 will not have this problem. You can work around this by finding where you are going using hotel or airport wifi. You can also look up a few addresses in advance, and they will be kept in the 'recent destinations' list. You don't need a data connection to route to already found destinations
In actual use, its quite nice. By default you get 3D view, and you can choose which voice you want, in a variety of languages as well.
And you can also see start to finish
So far, so good. Over the coming weeks I will test against a variety of addresses and routes.
One great thing is that since it uses Open Maps if there is something broken, you can go in and fix it.