Google should leave the EU. Drop an IP block and be done with it.
They could certainly rationally abandon the EU market if the fines continue to outpace what the entire EU search market is worth in profit. If you're Google and you can stay somewhere close to break-even on the fines, it's worth staying in the market just to suppress potential competition.
The ideal solution however is the for the US to respond by targeting EU companies, for example Volkswagen and Deutsche Bank (soon to be nationalized as it's collapsing) as two they've already very clearly gone after.
The fines for VW were at the country level, and besides the usual protectionism going on (one of the German states holds a blocking minority in VW by law, go figure) Germany also has a different approach to fines than the US, with much less emphasis on punitive damages.
It made consumers lives better, as well as business' lives. The only one losing in there were other shopping comparison sites, but no regulations were broken, yet they still had to pay billions, and the EU /didn't even/ bother telling them what they could change to fix the issue, just that they should do something about it.
The whole "follow regulations" excuse is complete bullshit.
They can respect the EU regulation, stop the crap in the search and Android and continue making money from the products they sell to enterprises. They will lose some profits but the products that are respecting the laws will continue making money.
That shows you that it's not about "respecting" regulation. It's about shoving it in their face and forcing them to comply.
I think the idea is simple, do web search, don't promote your video,maps, lanugages,services , don't add special code for Google products/services , and stop prompting people to install Chrome if they search with other browsers.
Why? They can leave the EU without IP blocks.
Just like China can be upset with Wikipedia. Wikipedia can tell them to pound sand.