I think the thing the worst thing Google does right now is its search. I challenged myself to use Duck Duck Go (DDG) for a month and after a month I'm still using it. The only thing I miss about Google's search are the occasional fun Google logos on holidays. But that's it! There is no real difference. I still find the content I'm looking for, etc.

What that tells me is that yes, there is great room for new search engines. I hear whispers about a super elite team at Google that does amazing algorithm work and data analysis work to keep their engine going, but at the same time I'm getting comparable results with Bing, DDG, etc. Several times people have posted a link to blind search where you see the results without the branding and it becomes difficult to discern the difference.