At the time Alta Vista - which was then something like www.altavista.digital.com - had been the most useful search engine, but had recently started taking money for good placings. Ooops. Once this was realised, its credibility vanished.
AV's low-crap interface had become a lot more complicated too. Like Yahoo, it wanted to be a Gateway - ker-ching! - not a search engine, because how would you make money from that, apart from accepting bribes for top rankings? Ooops.
So Google came along at exactly the right time. It produced very good results, very quickly, with no fuss.
The things that experienced AV users missed at first - the ability to say 'give me a page with this AND (that OR that)' or '.. starting with this' - turned out not to be a problem because it was so fast you could do two Google searches in the time it took to do one AV search.
And the results were almost always spot on... before people started gaming their algorithms anyway.
I'm not at all surprised 'google' has entered the language as a verb.