What actually created competition for the telephone network was the internet. Competition from cable and satellite and cellular.

That's what you need. Something similar but not exactly the same, so they can each carve out a niche and provide a backstop against the most flagrant abuses but they aren't in such direct competition that they're more inclined to cooperate than compete. So that you have companies who can make choices knowing that their position is different than their competitors and the competitor can't just mirror their action to neutralize its competitive advantage, which otherwise removes any incentive to be the first to engage in pro-consumer behavior.

Would it be “better” (given the regulatory goals) to order Google to do XYZ and provide an audit trail to demonstrate compliance?

Putting pressure on Google requires seriously increasing competition.

Let the local units rebrand and compete against each other. Maybe even auction them off to other big players. Whatever needs to be done to even the playing field. Google need a nice kick in the ass for their own good health.