I think we can have a good go at this by focusing on baby steps. We’re not aiming for Google, but a path towards building structures that make it easy to find stuff. So forget search engines and look back at how web search evolved.
I wrote something about this a few weeks or months ago but can’t find it now, but I recall that it was something along the lines:
-
people would find things by various means (word of mouth, lists of lists, curated topic lists etc). Individuals or organisations created lists for others to find things on their sites, these were shared and lists of these became bigger indexes, and it was fun collecting these and building bigger and better lists. Enough people will do this with no incentive except the desire to create. So that’s stage one - simple random sharing of lists made by others. We still have this today with stuff the search engines don’t index. This is a great opportunity for app developers, to build things that help people create and share lists in formats that other apps can consume, and in turn generate nice websites at the push of a button.
-
more curated indexes. I remember there was one semi-official list of websites by category, sub category etc etc. It may still exist but I don’t recall the name. Anyone wanting to make their website discoverable would submit a listing and someone would review that and hopefully add your website to the big ‘official’ list.
-
alongside that came simple crawler based search, AltaVista and I think Yahoo! More centralised, but still many engines, gradually improving and growing until Google invented the ‘page rank’ algorithm and the monopoly struck. This made all the other approaches obsolete and most engines lost almost all their traffic to Google and here we are.
With SAFE we are back at square one, so let’s start with that and assume enough people will just build and publish their own lists. Others will curate them, and curated lists will be curated and repackaged in various forms including searchable indexes, and no doubt there will soon be crawlers and even some clever ‘page rank’ stuff.
Now we can do better than this, but I think it’s a fair assumption that we’ll have the above to build on. We don’t need to incentivise everyone, but we can build engines that reward those who do this work. Just don’t reward them to the extent it is worth gaming.
That’s where I’d start. Build tools to help these processes, and to help pull indexes published in say, RDF together and will get more tools and new ways to do this without a monopoly.
Find ways to include the web of trust for topic based indexes, topic blacklists, topic whitelists or ranking etc and things can improve further.
Focus on things that promote decentralised control and wider distribution of rewards to reduce incentives towards monopoly and corruption.
Now I see Josh has also replied, TLDR: what @joshuef said! 
Oh and just so it doesn’t get lost: