Infoseek was definitely the Google of its day back in the mid-90s.  I loved that search engine and it was a shame to see it go under the way it did.  AltaVista also had a nice run in the late 90s and turned in decent results.
The thing is, a lot of search engines turn in results on par with Google these days (like FAST - alltheweb.com, Teoma, Wisenut) yet most don't seem aware of it because they're so infatuated with Google.  Personally, I think Google's results page is looking a bit dated and needs a little freshening up.  I like simplicity, but their's is SO plain that it's hard to quickly cypher through the results text sometimes because it all bleeds together.  Yahoo uses Google results and I've actually been using them as my search basis lately because I like the design of their results page better.  With the exception of the paid listings at the top it's a lot easier to read and scan through IMO.