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 :( .