The simplicity was important but more as a signal of quality.

I remember being frustrated at Altavista's or'ing of all your search terms; it often made attempts to refine your search counterproductive.

Google's results were just amazingingly good in comparison.

Also ..

DEC saw Altavista as way to publicise its "giant" computers. Eight Gb RAM back in 2000ish was amazing. But I and so many others could see that search was eminently suitable for a parallel solution. Using single (or few) large computers was missing an opportunity. This just reflected badly on DEC and Altavista. And I was reminded of Ken Olsen's famous quote of there being no need for a computer in the home. (unfairly apparently - it was taken out of context) It added up to a bad image.

Actually I remember my first experiences with Google. It was very weird for me that the page was so empty and I kept using AltaVista and later MetaCrawler. They seemed to be more 'serious' :D However more and more I've started to notice that the most relevant links are provided by Google and that was it ...