I tried no root firewall and found that Google groups literally everything under a kitchen sink service that talks to blind IPs with SSL. There is no way to allow Maps without inviting Google to share your bed with you.
What I mean is you wipe the phone, reinstall either AOSP or LineageOS (or other custom ROM), do NOT install any Google Apps (to include Google Play Services, Google Store, Google Maps, etc.). Use F-Droid (https://f-droid.org/) as your App Store.
I have been using OsmAnd (https://osmand.net/) as my map service.
I saw a very interesting talk last year about how Google Maps is often useless in third world areas, and OpenStreetMaps provides the only useful coverage.
It's due to armies of volunteers mapping an area during disasters, while Google has no economic interest in mapping the area.
https://media.ccc.de/v/emf2018-157-how-the-internet-has-chan...
Google has an economic interest in mapping anything as long as it's useful to some people. Google is playing a very long term game: provide free services online (Email, Maps, Search...) to entice more and more people to go online. The more Internet users there are in the world, the higher their ad revenues are. It's that simple.
I don't doubt your experience.
The talk is about disaster response, so it only describes maps in regions where a response is taking place.
Elsewhere, the rest of the time, I'm under the impression there is no serious mapping taking place, neither by Google or OSM.
What I found surprising from the talk I linked was instances where there was a hardly usable Google Map to use for the area (just big expanses on the map and the occasional large feature), and the fact that at times up to 1000 volunteers would work together mapping a region at short notice, down to street and building level, by analysing satellite images, and coordinating with responders on the ground.
In the opinion of those disaster responders, those volunteer created maps were much more useful than the Google ones.
We haven't exactly had one of those in decades, so yeah. I'd say it's a bit telling that there's only interest/means for volunteers to map the developing world when there has been a disaster, but I digress.
Google Maps is perfectly usable where I live (apart from its continued if understandable confusion about how...irregular roads and road access can be here), and in my experience has been at least useful in all the cities in my home country I've visited. OpenStreetMaps is...not.