This is the core republican (as in the political philosophy: Discourses on Livy, Philip Pettit, etc.) insight. If you want a stable society, you cannot leave space for arbitrary private individuals to become domineering forces on the rest of society. It's literally textbook how civilizations will fall, yet as a species we seem incapable of avoiding our own mistakes.
Sure, the government has more power, but it is also more constrained. There is no public control of Google, it is not a publicly sanctioned power.
Google is many orders of magnitude less likely to kill someone (legally or extralegally) or seize their assets than US government.
Whether you believe it or not, you have a lot more power to influence government (locally at least) than you do to affect what Google does. That was my only point.
Pay-per-search would be cheap enough for municipalities to negotiate subscriptions for their entire broadband network as a part of broadband service.
Yeah, the last thing I would want my search history to be tied to is my payment information.