Earlier quoted context omitted.
Maybe the problem with the Google deal is that it's exclusive: if you want to make one device that's Google approved and contains the "highly valued" services, you are disallowed by the compliance contract to make other Android devices that are not Google-approved.
Yep, that is a big problem. If company A has launched an official Android device, and company B goes to A and asks them to build a totally unrelated Android-based (but not Android proper) device for them, A is not allowed to do that by Google.
It's not hard to become a phone maker these days, judging by the sheer number of Android OEMs that are out there (hundreds, I believe). If there was huge untapped demand for Android sans Google then a new company would appear, they'd download the Android code, they'd go to Shenzen and do a deal with a white label manufacturer, and they'd make such phones. Google wouldn't stop them because they'd be a company that doesn't make any other kinds of phones.
We know this is possible because there's one huge market where that's normal, China. Google's services are blocked in China anyway, so there's no point adding their app store or mapping apps. Local firms produce local versions of Android for their own market and it works fine. We also know this because Amazon tried it and they weren't sued or anything.
There are also open source spins of Android that have custom app stores like F-Droid. A new phone maker could ship those too.