nothing would change except it wouldn’t be under Google anymore.

That's a massive change.

Google is an ad company, so they have a vested interest in knowing what apps you use, how often you use them, and perhaps even what you do with those apps. Splitting that off means the app store needs to sustain itself without the massive ad network (I suppose they could sell the data).

It could even be split three ways:

• Google - all the search and ad stuff
• Android - just the OS, which survives based on license fees to manufacturerers
• Play Store - just the play store

That way the Play store would need to compete with alternatives, like vendor-specific stores and FOSS stores. Whether that's desirable is certainly up for debate, but it would definitely be a significant change.

Change phones. Problem solved.

That's a duopoly, so no, the problem is absolutely not solved. If there were more than three phone OS options, I'd agree with you. But right now there are pretty much just two major ones, which means they can get away with a lot of nonsense because their customers really only have one other option.