[joshvm]

I find OsmAnd to be OK in a pinch. I use it a lot abroad with full offline maps (the fee is less than $10 a year, bargain). You're right that search is bad. Often an exact search for a POI doesn't work, and it only shows the "increase radius" option. Generally search is very viewport dependent, which makes sense because there isn't a massive caching/index server managing geo requests. But, for "where am I" when Google refuses to cache anything, it's invaluable and there are nice plugins for tracking/logging trips.

I was in remote NZ without reception and we used it for navigation/routing. It wasn't the most efficient and Google disagreed when we finally got signal back, but it got us to where we wanted to be and the map was up to date enough.