Definitely GrapheneOS.

Re-Google Maps: I use Here We Go, it is much better than the open street maps apps, has live traffic data, and reviews. Unfortunately needs to be downloaded from Play Store for use with Android Auto though (not even Aurora works).

I recommend using a separate user profile for work.

GrapheneOS but check banking apps again because for me they were working till last year but then Google started enforcing Play integrity check instead of SafetyNet checks. I was able to do almost everything from website so there’s that

Which phone should I pick up to run Graphene? like which do people like for this best?

Nice thing about graphene is that you can put Instagram and the like in a different user but for some reason I can’t figure out how to get my sim to work while I’m using the other user profiles

Graphene runs every app I’ve tried, no issues.

Graphene.

I wish I could use Graphene, but the pixel’s pitifully small and expensive storage to force you into cloud storage really makes an SD card necessary. I have around 200GB on my phone + SD already(including OS), and I don’t want only 50 GB for more photos and music in the next 7 years WITH the more expensive option…

GrapheneOS devs have a very “I will tell you what to like, and you will like it!” attitude, which results in UI and navigation choices that bug the crap out of me.

But I have to admit that for security and privacy it ranks at the top.

GrapheneOS. It gets updates and security patches quickly, it fully removes dependency on Google services (unlike any of the others you mentioned), and it is heavily deblobbed of proprietary blobs. It is rock solid. Here is a comparison table from a trusted third-party: https://eylenburg.github.io/android_comparison.htm

All of those apps will work, just install Sandboxed Google Play. Install company apps either in a Private Space or a separate user to isolate them. I recommend putting all Gapps (play store apps) in a Private Space.

GrapheneOS is the best mobile OS. Even though the Graphene team has weird habits of communication which might be off-putting for some, the OS technically still is the most secure AND most private mobile OS distribution you can have on any phone. It’s literally at the top, according to many technical and data protection experts. It’s so good that Cellebrite can’t crack it even with physical access, and some police in some country (I think it was Portugal) will assume you’re a criminal for using it, because it’s so secure and private and they can’t stand the thought of someone fully utilizing their personal rights. Plus, it has great documentation and is easy to install. Despite it being so secure and private by default, it still allows you to shoot yourself in the foot by installing the sandboxed Google services and so on, if you really want to. So it can also be used like an off-the-shelf Android, just with some additional hardening and extra protections on top which you benefit from, but the benefit will be much smaller of course when you install and use spyware apps.

For privacy/security, there really isn’t another choice: Pixel + GrapheneOS.

I love Graphene, because I seriously care about privacy. Everything works well but I also wasn’t a fan of having to find Google hardware. Second hand worked and next year I will consider the Motorola that will run Graphene.

Since you insist on Meta and Google Apps, you seem less concerned with hard privacy, so a Fairphone with e/OS could be a great choice. e/OS is nice too, I tried it for a while but found some laps in it’s privacy settings and I did not want to leak any location info to google.

If you don’t like it, you can revert to stock android, no problem.

I’ve gotta recommend GrapheneOS. As you’ve already researched, your apps will still work, even down to company portal which is working on my Graphene’d pixel I’m typing on now.

And I’m sure someone else has commented the same, but yeah, you can revert to stock if you want.

Teams works fine on GrapheneOS.

I recall Google Maps working briefly before I fired it in favor of buying a dedicated hardware map solution.

If they do work, which De-Googled OS should I go for?

Depends on your needs, I suppose.

All the options you’ve listed are an improvement over stock.

I had an old spare pixel to try out GrapheneOS, and it was faster than my newer phone, so I started buying GrapheneOS-ready hardware from then on.

I put LineageOS on some other hardware, and I miss some privacy features, but it’s still pretty nice.

Lastly, if I install another OS and regret it, is it possible to install the stock OS again?

Yes. There’s instructions to take a back up, at the start of the process.

My plan was to fall back to eOS or LineageOS if I hated GrapheneOS, but it’s been lovely.

Edit: Also, what happens after Google’s “Unverified App” decision has passed, will this affect these alternative OS?

That’s all part of Google’s app ecosystem. Install F-Droid or Droidify, and you’ll be immune to all that. Aurora may work as well, but usual disclaimer for Aurora - it relies on Google and might break at any time.

GrapheneOS has made public statements GrapheneOS itself is unaffected.

1. Regarding Google Maps, you might wanna try “Here WeGo” which is by a company in the Netherlands and more privacy friendly than Google.
2. If your primary goal is security and privacy, GrapheneOS is your best choice. LineageOS is good, if your device does not support GOS; I have no experience with /e/OS in terms of usage.
3. On Google Pixels it is possible through official methods to install Stock OS again, same for Fairphone. I don’t know about other devices.
4. Alternative Android Distributions like GOS, LOS and /e/OS won’t be affected, except if you install Google Play Services (and related), though GrapheneOS will likely limit it with their sandboxed method if you do so.