If another water company wanted to come in and install pipes to your house, they would be prohibited from doing so.
Other search engines aren't prohibited from competing with Google -- in fact many countries actively encourage and fund local competitors -- so I don't see how this analogy makes sense.
Maybe monopolies should have their products strictly regulated regardless of how they came to be monopolies?
Other way to deal with monopolies is just force them to split up into few companies, but I don't think that users would benefit much from having 10 different search engines to choose from same way they don't need their browser to have 10 different homepages. They need just one, but the one that provides results that they need. Same way like they need one water provider that provides the water of quality that they need.
If you allow Google just to show results from whoever pays the most, that only shows that they are sitting on the bridge and let pass through only the ones that pay the most, no matter how much value their passing brings to everybody else. At some point nobody cares if they built this bridge or not. Their bridge stands on and occupies optimal spot for a bridge so people on both sides of the bridge should and have every right to fight for such agreement that benefits them most, not just the bridge owner/constructor.
They could just wait to clean up their act once they see competition on the horizon (or just go through the motions), which would more than likely scare that competition off. Building a water utility isn't cheap and I doubt there would be enough profit in a competitive environment to justify the cost.
I get my water from a private company. Should they be forced to supply me with clean drinking water, counter to it's financial interests? Presumably it would be cheaper to just pump it out of the river into our homes?
And that is the problem, Google has risen to utility level dominance, and utility level importance. Millions of peoples jobs rely on search and search results, time for regulation.