However, the lean interface without blinkentags and ads was definitely a selling point. Also, IIRC, the guarantee that you'd only get sites that actually contained all the words in your search query (that feature is long gone, too, of course).
The interface and speed were great, no doubt. Did you ever encounter another search engine that produced similar or better results that you otherwise would have used, but Google's interface sold you? I never did, so it wasn't a selling point for me.
It was a big contrast and a signal of classy goodwill, back in the age of replicating popups and garish blinking text.
I would have put up with slow bloated adware Google results of early 2000s, compared to fast minimal sleek interface with results of Yahoo/Altavista/anything else I tried.
There were lots of "differentiators" that did not really matter, including speed. The differentiator was result quality, not how or when they were presented.
If, back then, Yahoo and Altavista were minimalist and Google was a garish nightmare of ads and flashing gifs and nested banners and affiliate buttons, I would still have happily used it for the results.
Google's search interface is still reasonably clean IMO. Nowhere near its minimal best. Yes there are ads and "sponsored results" and shopping frames and all that crap, but they really aren't everything that's wrong with Google Search.
Quality of results and inability to specify queries beyond vague suggestions are the worst things.