I think the best path to a "Google replacement" is probably to reinvent Yahoo or dmoz. You'd still have to human curate the worthwhile sites through a ton of SEO spam and, if you go the dmoz route of volunteer curators, that's an attack vector for spammers but I think it'd be much more manageable than trying to build an index of the entire web and search it. A new general purpose web directory would also help mitigate probably the biggest harm that Google's algorithm has caused to the web: the death of the "links" page as a standard part of a web site due to sites trying to increase their pagerank by reducing outbound links.