For my purposes, that works out well, there are, within reason, replacements for all the basics. And now that I have done it for so long, I don't really know how having an android phone with google works. The niche is big enough that something like https://microg.org/ exists that implements some of the core libraries for using google, without using google code. This enable installing some things from the playstore if neccessary ( I have not had the need - but I understand I am in a tiny minority ) - and it made it possible to install some corona contact tracing apps without having to rely on the google implementation.
I am sure though, and I see it around me, that things won't continue exactly as before just without google, because of how deeply ingrained tracking everyone and everything all the time is.
I don't know how hardcore you wanna get, but you might also want to take a look here https://e.foundation/ , here https://lineageos.org and here https://f-droid.org
There's like - dozens of us
...and thank you for reminding me of ParanoidAndroid. I've not tried them in a while.
CalyxOS turned out to be about perfect for my use case, and I've been incredibly happy with it.
They have a flashing tool, which basically involved me plugging my phone into my laptop and running a script. Only thing I really needed to do was follow the prompts.
This isn't a bad thing. Society is built on trust. All it means is that there needs to be consequences for breaking that trust, to keep everyone honest.
I used paranoid android in the past and it definitely isn't privacy focused. The name makes it sound it's privacy focused but that's about it.
The trouble with privacy as a product is that it's _very_ hard to verify it. Apple has basically said "Trust us, We're Okay" and smaller fry are even harder to verify.