Google became better than everyone else but that only happened AFTER they became popular. Altavista was initially as good or better.
From what I recall at the time, Google was initially a good quality engine, but Altavista had a huge lead in the size of their index. At the time, the size of your web page index was considered the biggest factor in search quality and ranking algorithms were... important, but considered secondary. Once Google's bots reached a critical mass, their algorithms won.