James Svoboda who has completed 10 years working on SEO related activities recounts his experiences with Search Engines in the pre-Google era and it makes for interesting reading. He talks about Meta Search, Web Directories, Pay Per Click, Affiliate Programs and catastrophic SEO events like AltaVista’s Black Monday, Google's "Florida" Update (both events are the SEO equivalent of a stock market crash due to a change in the Ranking algorithms)
As far as I can remember, none of the search engines then were even as closely minimalistic as Google nor as fast. I used to frequent Ask.com and try out other search engines if I didn't get any results there. For searching code, I used to depend on the now defunct CodeHound. After Google got popular, I mashed-up a custom Javascript application to fetch results from my favorite code sites.