What else can Google do to be less Evil?

Google recently scored an extra point in the "Not Evil" column when they announced they're essentially leaving China.

But what else can Google do? Let's take a page from one of Roger von Oech's Creative Whack cards, and play the "What If" game. What if Google had no ads? And not just the ads on the right-hand side of search results. What if they also had no AdSense ads that appear on the publishers that Google inevitably sends you to as well?

Bob Pritchett wrote:

There's an opportunity here to create a web search engine that punishes results littered with ads. Google can't do it - they live off those ads. A site that took ads but didn't have an incentive to send you to other sites full of them could offer a superior experience. (via)

If you turn the clock back to 1998, this is precisely what Larry Page and Sergey Brin wanted to do. They outlined this exact issue in a paper they presented as part of their Ph.D. requirements:

Currently, the predominant business model for commercial search engines is advertising. The goals of the advertising business model do not always correspond to providing quality search to users. For example, in our prototype search engine one of the top results for cellular phone is "The Effect of Cellular Phone Use Upon Driver Attention", a study which explains in great detail the distractions and risk associated with conversing on a cell phone while driving. This search result came up first because of its high importance as judged by the PageRank algorithm, an approximation of citation importance on the web. It is clear that a search engine which was taking money for showing cellular phone ads would have difficulty justifying the page that our system returned to its paying advertisers. For this type of reason and historical experience with other media, we expect that advertising funded search engines will be inherently biased towards the advertisers and away from the needs of the consumers.

(via Googled by Ken Auletta)

There was a point, maybe five years ago, when it seemed like everybody had positive things to say about Google's search engine. Now when they refer to it, it's often to imply that it's a necessary evil. And when you have such massive and widespread frustration, that points to an equally massive opportunity for a new upstart.

But which startup will fill the vacuum? Bill Gates famously once said that the competitors he worried about the most were a couple kids in a garage. But who would be the equivalent "kids in a garage" to Google?