At the pretty wired (ok, it was in Minnesota) .com startup I worked for in the 90s I was the first to discover and use Google. Alta Vista, my old favorite, had been in decline and Yahoo was still pretty much a directory/indexing company (for manual indices, I then preferred the Encyclopedia Britannica's site!).
Google was the clear winner from the start. It's been a Google world ever since.
There are rumblings, though, of rebellion. Googe's indexing engines are slow to hit many pages, especially Gooogle's own blogs. Yahoo seems to hit the pages Google misses. And, as Phil Bradley notes, there are many special purpose alternatives.
Here are a few I've lately found useful - or at least interesting:
Mindset (Yahoo): Yahoo search biased to commercial or non-commercial
Grokker: visual results
Brainboost: just facts
Google Scholar: academia
Google Portal: Google + Gmail + Google History search
Froogle and Pricescan: Shopping, also Amazon for the best overall user reviews.
Google Print: search full text of books
(added 5/28, thanks to a reference from Phil Bradley's blog)