Google the search engine is critical internet infrastructure, and innovation into it is stagnant from a user's perspective.

It is not internet infrastructure at all. It's a consumer tool, potentially about to be replaced by AI.

Another thing about utilities: water or electricity are fungible goods, easily measured. Search is rather trickier to decide what a good outcome is, and the thought of paying for politicians and administrators to debate search rank orders for eternity seems a terrible use of money.

Finally, things like water supply have been around for tens of thousands of years. Thinking search hasn't done so much in the last 10 maybe be a little short term! Thinking it will be around in the long term at all, and thus worth converting may also be a little short term.

The average consumer's experience of the Internet would be drastically altered if Google didn't exist. From the functional standpoint of a user, Google is internet infrastructure. Whether it's a utility or not is a different question, but I argue that it is definitely internet infrastructure since people's life and usage of the web would very disrupted without Google. It may end up replaced, like the phone was. That's not relevant as to whether people use and rely on it like infrastructure.