To google something has become a verb. Google search is the overwhelmingly largest source of traffic for many sites. Google’s market share in most markets is higher than its competitors combined.
Google has brand identity, search quality, technological quality, and page speed down pat.

So how would you compete with Google search? (Not that google search is bad, but a little friendly competition is always a good thing, and it’s interesting from as a thought experiment).
Frontal assauls (doing the same thing as google, but trying to be better) like yahoo and MSN have hugely failed. In fact, dominant market positions are seldom eroded by frontat assaults, but rather by changes in market demand. The reason why Microsoft has lost so much influence to Apple is not that Macs have replaced windows (globally, Mac OS still has a tiny, if profitable, niche of the PC market), it’s that the market demand shifted so that the whole category of PCs became less relevant since the introduction of smartphones and tablets. Likewise, if ebay sales decline, it won’t be because somebody builds a better auction site (network effects are just too strong for that), but because somebody invents a better way to sell stuff than auctions (like the ability to sell used books back to amazon).

So what are Google’s weak points?
– google does not trust humans -> it cannot use e.g. a human-generated catalog
– google is the no.1 target for spammers, the same way windows is the no.1 target for malware -> a smaller rival might be unnoticed/not worthwhile for spammers, and therefor be able to offer better quality, at least for a while
– google sucks at / has no customer service. That is a good thing, cost-wise, but also keeps people away that require more hand-holding.
– google is run by engineers, so it under-values things like design, and other emotional, touchy-feely topics.
– google is huge, so serving small niches is not interesting.
– google does not understand multiple meanings of a word (for eample, “go” could mean the game, verb, or programming language) – although that is probably the kind of hard compsci problem that google is best at solving

Ideas for competition:
– give me LESS, not more, results (but probably not from a huge human-generated index – that idea failed with the first iteration of yahoo…). E.g. when searching for reviews, google gives me spam and shops (yuck) and reviews from the big newspapers, what I want is 5 blog posts from people like me who have bought and used it, or a link to a great site like kenrockwell or dpreview for cameras)
– serving a single, canonical result. A lot of times, when I search google, I’m looking for something specific – say, the download link for a certain program, or the website of a known organization. Google is pretty good at finding that, but also gives me a lot of results I do not want, which sometimes leads to unwanted results (for example, there were some cases where, due to clever SEO, people looking to download the VLC video player got sent to sites that charged for the download). Finding those canonical links would be labor-intensive, but maybe you could farm it out on the cheap on amazon’s mechanical turk?
– serve a niche very well (flight search or weather are separate category from general internet search, what else can be served by a non-general search site? (technorati for blogs failed…)
– do something sales/service-intensive, e.g. a service where you need to sign up local small businesses. Needs a large salesforce, and therefor large investment, but e.g. yelp has done that successfully.
– rank pages by reputation / social links. For example, when evaluating some product or technology, it would be great if, instead of wading through a sea of marketing drivel, I could get all the links posted by people who follow people who I also follow on twitter, or articles written by somebody whose writing I previously flattered or saved to instapaper. Sort of the holy grail of the internet, apart from being a massive privacy headache.
– better, complex tools for slicing and dicing data, not just finding facts (cf. Wolfram Alpha – which launched hugely mispositioned as a google search competitor, but is actually great at certain specialized tasks)