- Crawling and document parsing. Imagine something like archive.org where all search engines would get the content from. This could also be used to enforce copyright legislation (e.g. deletions of documents, etc...). Today, it's nearly impossible to collect the data as google does, because most website owners won't even allow that you crawl them (e.g. distill networks anti bot protection, etc...)
- Metrics (e.g. data from google analytics, dns resolvers, browser toolbards, browser statistics, etc...). Again this data should be available to everyone from a central authority.
Then there could be more independent search engines building on top of that data. If that doesn't happen, then there will never be any competition. Todays copyright and data privacy laws even further strengthen a monopoly position, as smaller players will not even get access to some data (or at different pricing then google does)