Altavista attempted to do what seemed like the obvious thing, and what most search engines did early on: it attempted to make hard searches easy.
Google's brilliant innovation was to do something far more useful, but less obvious: it attempted to make easy searches easy.
Put another way: Altavista competed with other search engines; Google competed with your bookmark file.
Back in 1996-97 I used to live by my bookmark file. Far fewer companies had actually managed to get hold of their company names as domains, important sites were tucked away in nonobvious places, and just finding what your were actually looking for was such a relief that you felt some real urgency in bookmarking the site and remembering how you got there.
In that time Altavista could almost always get me where I wanted to go, but often I have to look on page 2 or 3 of their search results for something that should have been on page 1.
Then came Google. Sure, the Web had evolved, and companies had figured out how to get their sites onto more intuitive domains. But mainly Google did a great job of making obvious things easy to find. Their "I'm feeling lucky" button is by far the link on the Web that I click on most often. I still have a bookmark file, but I hardly use it. My bookmark file loads only slightly faster than Google, it's less complete than Google, and frankly listings are in a more useful order in Google than they are in my bookmark file.
But let's not lose sight of the fact that early on in their competition, Altavista was _better_ than Google at what Altavista was trying to do. It's just that Google was trying to do something more useful. When it came to really hard searches -- looking for a particular file name used within a particular Linux device driver source tree, or looking for an old classmate when all you have is a very common last name, a place they used to live, and a hobby they used to have -- Altavista beat Google hands down. And no one to this day has an advanced search syntax as sophisticated as what Altavista had, despite the crappy (and undocumented) interface.
No, at the time that their Raging Search was launched, their best attempt at a Google competitor, they were better for _hard_ searches.
Google had gotten better, even at the hard searches, and Altavista hasn't been maintained. But this is a sad day.
The opportunity is still out there. Google will continue to win the competition with my bookmark file. But someone could still do an uncluttered, no-ad or low-ad search engine, aiming to make hard searches easy, and do better than Google. It's not as big a niche as CMGI needed, but it is a niche worth having.