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.
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.
I knew I forgot to mention some things. So far MAPS.ME has been an acceptable replacement for navigation, and its performance has been surprisingly good. I still don't like being tied to a closed source mapping app though, so I'm going to give OSMAnd a spin as well.
The battery life surprised the hell out of me, especially since I spent a couple of hours getting the launcher set up the way I like it. It's telling how much battery and data are used when your phone is constantly in contact with the mothership versus a device that only connects to a service when you strictly allow it.