It’s interesting that you say that the Google Play Store can’t be avoided on stock Android. I bought my current phone brand new from the store years ago, and the first thing I did was block the Google Play Store, and download F-Droid and Aurora.
I have never downloaded a single app from the Google Play Store on my phone, and I never logged into any official Google apple except Google Play Books after a couple of years. It’s the only official Google app I use, every other “Google app” is/was a modded app.
For years, I never had any issues from blocking and not using the Google Play Store. The only app that gave me any issue at the beginning is 1Password. The specific problem I had with one 1Password, and still have, is that whenever I scanned QR code to import a 2FA token, it didn’t work. I always had to manually add it, I don’t know why.
Then after a couple of years, a few other apps stopped working. Just 1 or 2 if I remember. But most of the apps work fine.
It’s my understanding that GrapheneOS works best on a Pixel phone, and I don’t have one. I find them a bit too expensive. Morever, as a newbie, I admit that I am nervous about installing GrapheneOS. For me to be comfortable with it, I would have to have a back up phone just in case something goes wrong.