DeGoogle Yourself

Try Insular which lets you install Play Store inside an island that is essentially a bare android system. If the apps access anything on the operating system like contacts, etc. they just get empty data (unless you populate that islands Contacts with what you need for an application). You can make multiple islands if you need to isolate other applications from each other, or you can just install all untrusted apps inside of one island and let them feed off each other. I've also seen people poison the data those applications get with bullshit data in the things they are accessing inside the island and sending back.

I've used this very successfully with GrapheneOS, it'll run my bank app for instance, so I don't have to keep Play Services on my mainland profile. You can also move apps from mainland to island, or island to island inside the Insular manager.

Microg may work. I am a little surprised it doesnt work if you havent disabled play services. I generally avoid mainstream apps and use mostly apps from f-droid to not run into issues. Lord only knows what data the ChatGPT and other apps like it are collecting without you knowing.

Was a while since to tried to do it by removing. but removing stuff is not as good as starting without them. Easiest way is to flash a custom ROM. Then you can add play compatibility with MicroG or playservices isolated by apps or GOS ( if you have the right phone that's it).

You don't need root to run a custom ROM or run MicroG. You might need to root to flash everything depending on your phone , but no need to re enable it afterwards.