I find OsmAnd to be OK in a pinch. I use it a lot abroad with full offline maps (the fee is less than $10 a year, bargain). You're right that search is bad. Often an exact search for a POI doesn't work, and it only shows the "increase radius" option. Generally search is very viewport dependent, which makes sense because there isn't a massive caching/index server managing geo requests. But, for "where am I" when Google refuses to cache anything, it's invaluable and there are nice plugins for tracking/logging trips.

I was in remote NZ without reception and we used it for navigation/routing. It wasn't the most efficient and Google disagreed when we finally got signal back, but it got us to where we wanted to be and the map was up to date enough.

I also run GrapheneOS. Did you have to install Google Play to be able to install and use Magic Earth?

I'm trying to keep my phone as de-Google'd as possible.

That said, the one thing I miss from proprietary Android land is Google Maps so I am very interested in a comparable alternative. I'm trying Organic Maps at the moment, and had played with OsmAnd~ but found it lacking when I tried to use it for real-time navigation while driving.

F-Droid → Aurora Store for all your Play Store needs. No login needed.

Thanks!

Do you get many apps that complain about not having Google Play Services installed? Just had one (not Magic Earth). Seems to work fine after I hit "OK" to dismiss its message. I'm assuming it only requires it for auto installing updates.

Google Play Services implements a lot of increasingly vital features and interfaces on Android. Not having it kills a good number of things people consider important, like push notifications (some apps are designed to still send push notifications like Signal, but it's kind of a hack and does drain the battery). If you're looking for almost the same functionality without google play services, MicroG[1] is an open source implementation of Google Play Services and its' associated components. I don't think it works on GrapheneOS unfortunately, but GrapheneOS already sandboxes all the Google Play Services components, so you should be fine as is. "Normal"/stock Android roms aren't set up the same way however, so you pretty much need either Google Play Services or MicroG for push notifications, location services, etc.

[1] - https://microg.org/

I do but ordinarily for services that are not anonymous in the first place. Banking, ride-sharing, so on.

You probably know this by now, but it doesn't require any Google Services to be installed in GrapheneOS. I did install through Aurora, but you could just get the apk and install it like that.

Here is a crazy fact... Google Maps doesn't require Play Services to be installed. About once a week it will popup a message about no services installed, but it still functions (other than logging in).

In my experience this goes for most - for me actually 'all' but I don't tend to use much from the Play store - apps which insist on having Google Play services installed. They blatantly tell you to 'Enable Google Play services' because (e.g.) BankID won't work unless you enable Google Play services. Just click outside of the dialogue to make it disappear and use (e.g.) BankID as normal, it just works as it should.