You can run one of those os's without any Google services. Paid apps are almost certain to not run, and a bunch of other apps that rely on the services. But almost all the apps I use work great.

I have used CalyxOS and it's a great os. I did use microG and 98% of the apps I use worked flawlessly. If you have a supported phone, I'd definitely give it a shot.