Google was clearly better at the beginning. I remember those days, and how Yahoo! put a bunch of other search engines at the bottom of its own results (Altavista, Excite, Lycos, etc). So it was easy to compare. When Google showed up, it was pretty obvious the game was over.
AltaVista had support for boolean operators; I and many other techies became very practiced in composing complex queries. It was my favorite search engine.
Then Google showed up, and Google had PageRank. Boom, the top result for any simple query was what you wanted.
The main reason? "And" searches. Brilliant.