My current phone is starting to annoy me after 7 years of usage (Xiaomi Note 8 Pro) and I'm thinking of finally getting a new one.
With that in mind, I'm considering setting up a De-Googled OS as well, but there are a few things that I cannot compromise on:

• Google Maps (I need the live traffic data when in a hurry, otherwise CoMaps is very nice)
• Banking Apps (I've checked them in the GrapheneOS list and they do seem to work)
• Instagram (it sucks I know, but I like not being a hermit)
• Company Portal & Teams (absolute garbage, but I need it for work)

If any one of these aren't guaranteed to work, then it's not an option for me right now.

If they do work, which De-Googled OS should I go for? GrapheneOS does seem like the most private one and maybe the most likely to remain worked on and supported for a long time, but it means that I'm going to have to buy a Pixel, probably a refurbished one.

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

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

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.

my list is the same as yours (minus android auto) and i've been wondering the same thing so i have decided to offload the capabilities that i need on my current phone while tethering it to my new lineage or graphene phone.

it seems that graphene is more secure, but i hate google with a fiery passion so i refuse to support them in any way including supporting their second hand market. i've also NEVER had good luck buying second hand personal electronics so it would be foolish for me to do it again. also: my goal is to de-google and my privacy threat is the local police and ice; not the cia, nsa, the rest of homeland security or mossad; so that makes both graphene and lineage work for me.

on the other hand: lineage supports more devices, but i looked the other day at the most recently released phone models and pixels top that list too; so it seems that going w a pixel opens to door to letting you use both graphene and lineage if you decide that you like one more than the other.

i was going to purchase an e/os device from murena up until a few weeks ago until its ceo showed his stripes in public and made he clear that he's thinks that only criminals was this sort of security.

☝🏻This. BUT, if you can't wait until Samsung Motorola drops their GOS model, you might get longer life out of it. But GOS support window is pretty broad. Can't remember exactly, but I think it's 5 years. So getting a Pixel wouldn't be horrible.

EDIT: second time I made that mistake today. Must have Samsung on the mind. Love the fact that people down vote the reply even though the error doesn't change the message. Never change, basement dwellers.

Motorola not Samsung.

The bootloader will be unlocked with Lineage which isn't good if the local police and ice are part of your threat model.

I've been running GrapheneOS for several years now and I love it, and currently run it on a Pixel 9 Pro XL. Super easy to install and use. With respect to the things you can't compromise on, you should be fine if you run the sandboxed Google Play services. I will say that my banking app updated a while back and now will not work with GrapheneOS, saying something about a lack of security, which I assume is because they probably added checks for stock android, so YMMV. If you buy a used Pixel, make sure you get one with an unlockable bootloader. Carrier phones have locked bootloaders, along with carrier locking, and when they unlock them they just unlock the carrier aspect so that you can use them on other carriers, and the bootloaders remain locked so you can't wipe the OS and install another, so you have to make sure you get one with an unlockable bootloader. Some ebay sellers advertise this, making it easy to find what you need. If you ever want to revert to stock android, it is an easy change. Google's "unverified app" decision does not affect GrapheneOS' ability to sideload apps, as it is a completely different OS.

"considering setting up a De-Googled OS as well, but there are a few things that I cannot compromise on:

• Google Maps"

Sorry but ... is this a joke?

good to know; thanks.

As you are asking this in a privacy community I would say Graphen. But as you want to keep gmaps you might also want the comfort you get with e/os when also using their cloud. Personally I would recomend a used pixel 8 with e/os and to try mapy.cz to replace gmaps.
About going back to stock OS if you choose a pixel flashing images is stupid easy :) so no worrys there.

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.

Yes the unverified apps thing will affect you no matter what. It’s not getting better any time soon. There are a lot of reasons for that.

You can’t “de-google” if you are 100% married to googles navigation service. It’s gonna become much harder to avoid play services (the google play store and all its telemetry) if you need a banking app and teams even if they seem to work now because the “reasons” above.

Other people have said that “privacy is a spectrum” in response to the following unconventional advice, and that’s true! Your conception of privacy may simply be getting away from the default apps and keeping the play store! Just keep that in mind:

If you’re actually gonna do any of the things we consider phone stuff on your phone, in terms of privacy and security it goes graphene > appropriately configured ios > a big gap > everything else.

Maybe consider switching. There isn’t a big cost difference anymore.

Speaking from experience with both android and ios platfoms including many custom roms and the alternative repos/app stores, it’s much, much easier to stay as private and secure as possible on ios.

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.

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.

Even though the Graphene team has weird habits of communication which might be off-putting for some,

I like my secure OS developers to be on the paranoid side of sane.

It's probably not a stretch to think that there are a lot of people out to compromise that specific team of developers, that'd make me paranoid too.

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.

https://swappa.com/

Never had an issue with getting unlocked Pixel phones from them.

Yeah Google maps is much worse than OSM in my experience.

I agree --> Motorola just signed a deal with GraphineOS. I am pressuring my phone carrier to sell Motorola phones with GraphineOS to us and encourage you to do the same. I is low-hanging fruit to do an OEM deal with Motorola.

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'll simplify for the downvotes : "a De-Googled OS [...] cannot compromise [...] Google Maps"

Agree, but I get the live traffic part. It's pretty much a must in some areas. I think there was a wrapper/API but google killed it

You can also use google maps from the browser

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.

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...

Graphene.

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

the last phone i purchased like this from ebay never showed up and the seller, shipper and my credit card company all refused to take take responsibility nor would they re-imburse me.

the previous phone's speaker didn't work, so i tried to use the manufacturer's warranty to fix it, but they refused since i wasn't the original buyer and the person who sold it to me on amazon refused to refund me because it took the manufacturer weeks to respond. amazon also refused because of the time limit.

the previous phone kept overheating and shutting off randomly and the seller ghosted me and everyone else by shutting down shop so there was no one file a grievance against.

and that's only phones, i've had similar problems with laptops, ear-buds/head-phones, tablets, etc. so i refuse to buy any used personal electronics now.

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

Go to user settings/manage usersthere you can enable SMS and calls

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?

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.

Currently only Google Pixels are supported, but I would also like to know model recommendations. Is it worth getting a 9 and going beyond budget or is a 8 Pro second hand still good for its price?

I'll keep it in mind, thanks!