I'd read a bit about Cuil, a newly released search engine that is claiming to search more pages than any other search engine. It is developed by a management team that read like exactly the team you'd want if you were going in to this market.

Is this going to upset Google's party? Probably massively too early to say, but it is interesting. There seems to be some key differences in approach:

• The search results - appear in columns, rather than a list. There's also an image (they serach for the most relevant image - which I can confirm doesn't work well.) 
• Indexing - apparantly not by "pagerank" like google (inbound links) instead by relevance. Content is scanned for relevancy to any individual serach query. This does sound nice. Though, my blog isn't indexed. itself, only references to it. Perhaps a bit weird? You'd expect it to return the actual blog as well as references to it?
• (Not really an approach) - but you don't seem to be able to search by country - like you can on Google. Maybe that's because it is new?
  

You can read more about differences here.

Overall, I think its is brilliant that someone is having a go in this area. Google are doing so many deals these days (trying to provide serach results for Yahoo, maybe buying Digg, the list is endless)  - I am a big fan of theirs, but some healthy competition down the line would not be a bad thing...