In the later 90ies I usually relied on HotBot, which actually had better results than Google provided initially. Biggest issue, not just with HotBot, was the completely overloaded start page, which especially on modems made it slow to load. This very simple start page by Google was very intentional; for example right now it is almost 300kB, cookies and other such junk not included, i.e. based on completely different assumptions of the commonly available bandwidth (300kB start page would have been instant death spell for a search page back then). They worked hard to make the crawling + results better, and that was pretty much the final nail in the coffin for all the other options.