> The way some people use their iPhone (my partner included) and all the (cr)Apps they have and what they do, it may as well be an android phoning home to google

The difference is that with the apps installed on a phone, you can uninstall the app. With Android you can't just "uninstall" the Play Store.

Sure you can. You'll need to uninstall Google Play Services as well but it is definitely possible to run Android without the Google-specific bits. It's is the first thing I do when setting up a new Android-device.

This is not trivial and is not akin to simply uninstalling an app (coming from a google-free Android user on a pixel).

Out of curiosity, how difficult is this to do? Would the average user be able to do this easily?

It is distinctly non-trivial. Likely part of the reason why it remains possible. Chasing down bugs is the unavoidable result, but to a geek it's manageable. MicroG works very well once sorted. It is however astonishing how much processing power Play Services gobbles up. A de-googlefied phone lasts 30-40% longer on a charge. Once done, it works like a breeze. 3-4 year old flagships Androids are titans when de-googled and with custom roms.

This looks promosing - "New company called eelo will give you de-Google-ized Android so that you can keep your privacy"

https://www.phonearena.com/news/New-company-called-eelo-will...

If the phone can get LineageOS, then it is fairly easy - just don't install GApps when flashing LineageOS to the phone. Alas, phones that are thus open are getting rarer and rarer :( .