Maps.me is pretty good. Does offline routing using OSM data, allowing for downloading entire regions (~60-200mb). Also, recently went open source.

Doesn't have terrain details yet, but they're apparently working on it.

I use Scout http://www.skobbler.com/apps on Android. No complaints.

OsmAnd~ can do full offline search, navigation with per-country downloads. The f-droid version is unlimited:

https://f-droid.org/repository/browse/?fdfilter=osmand&fdid=...

Osmand

I actually thought this would be the obvious answer, instead it's near the bottom of the thread. Odd for the best open source navigation app I've ever found.

Just downloaded OsmAnd after switching to maps.me 6 months ago. They've made a lot of changes (for the better). Thanks for the suggestion

Yeah, it went from super nerdy to quite user-friendly.

Switched to Osmand today after Scout stopped working on Marshmallow with External SD.

I like mapFactor Navigator [http://navigatorfree.mapfactor.com/en/download] on Android for car navigation. The most useful feature for me is that you can search via Google.