[mabramo]

I can't speak for the above poster, but I will say that some GPS apps, such as OsMand, are quite good. The catch is that you have to download the map for your region to local storage and you totally lose search queries like "Find the nearest Wafflehouse". In addition, OsMand specifically has a bit of a learning curve to it where GMaps, among others, are search and go.

[dublinben]

While it doesn't have natural language searching yet, OsmAnd actually has very powerful POI searching. You can search for POIs by name or category, and have them displayed as either a list or points on the map.