I don’t see any mention in this article of what seems like the most obvious way to split up Google, separating their search and ad businesses. (Edit to add: although maybe the effect would end up being similar, if API users serve their own ads but without access to Google’s ad infrastructure.) That obviously wouldn’t be a simple job, of course, and maybe there are some interesting reasons why it wouldn’t work well.
Outlaw ad tracking in some way.