If I remember correctly, Altavista produced better results than Google back then, for me at least. However, Altavista took seconds to load the first page (on 56k) whereas Google's first page loaded almost immediately. I honestly didn't expect Google to have survived the dot-com bust back then. This was before they figured out online adword auctions.
Google was immediately better then anything else from day one. Google was launched in Fall of 1997. In January 98 is when I started using it and it was hands down better then crawlers or any other search engine.
So, funny thing: Back then, if one search engine didn't have what you were looking for, you would try another. Now, if Google doesn't have what you are looking for, where do you go? Does it mean the answer does not exist on the Internet? Do you try Bing or Duck?