I agree and have moved mostly away from everything Google. But it's hard to replace maps. I know open street maps exists but it's hard to beat Google's data gathering.
There are players in the OpenStreetMap ecosystem attempting to change that. I know the team behind Organic Maps are actively working to make their app as viable as possible by sourcing appropriate data for example.
I use Google Maps on Graphene. It works perfectly. You still get the benefits of the rest of the phone being degoogled. Just allow it to access your location only when you're actively using the app. When it's closed, it's closed.
I've been using HERE WeGo for almost a year. I had to install a text to speech engine in order to get voice directions. (I installed the GlaDOS one, now the evil computer tells me where to go.)
https://www.here.com/products/wego
I've settled on running CoMaps in the Owner profile, with Google Maps/Waze/etc. in the Owner profile's Private Space for when they're necessary.
I think OSM is way way better. It has every little path in the hills I walk. On Google Maps I'm just walking in a featureless green blob. OSM even has unofficial trails that are no more than a worn-down line in the brush.
Maybe for cars Google is better but I don't use those. But even there I see really detailed stats.
OSMAnd is a really great full featured mapping app. A real tool that you can configure in detail. And Organic maps is more simple and quick like Google maps.
There's just two things I still need Google for: most businesses don't bother keeping their opening hours etc updated on other mapping services, and in my city they have live data on the public transport network. This should really be mandated to be offered to open street map too.