I don't think many people stopped using AltaVista because it was too slow.
That's exactly why I stopped using AltaVista. I never noticed Google's search results being more relevant. I distinctly remember this because I was aware of the hype around relevancy at the time and was trying to notice a difference.
What was magnificently different, though, was Google's subsecond page load and search response times.
One interesting thing about marketing is that the reason one gives for using a product is often rather disconnected from its real utility. (The book Positioning is about this.)