Google was giving better search results during their rise to prominence because PageRank wasn't as vulnerable to spamming. They also chose to make their adverts unobtrusive and very clearly distinguished from the search results.
The search syntax was also pretty advanced. You had parenthetical grouping, logical operators, and if I recall, the +/- include/exclude syntax originated with (or was at least used by) AV.
What AV wasn't was particularly relevant. You needed that advanced search syntax to be able to narrow down what you were looking for, and you still usually had to go through a few pages of results to find the right stuff.
When Google first hit public beta, it was immediately and compellingly superior to anyone else's search. I remember giving it a few tries, and switching within a matter of a week or so. It just gave me what I wanted.
It took a long time for anyone else to get off the "but we need to keep users on our pages for ad clicks" mindset, and by then it was too late.