I use Google Maps all the time to not just navigate, but to find businesses and their information (are they open, etc.) I hear good things about Organic Maps, which relies on Open Street Maps, but a quick couple of queries shows several missing addresses to which I travel often.

I tried OsmAnd, but while it had a little more info that Organic Maps, it still didn't have what I'd need to rely upon it.

HERE WeGo had those addresses, and even some business info.

I haven't yet looked at Magic Earth

Ultimately it's going to come down to privacy vs. usability. I'm not yet sure where I'm going to come down on this issue.