I think the flashiness would not have mattered so much if Lycos's results had been better. If I recall, the search results I got from Lycos were poorer than WebCrawler or Alta Vista. There wasn't that much difference, though--every search engine's results were filled with spammy crap. Yahoo, Lycos, Excite etc. decided to attack the spam problem with brute force by creating human-edited portals.

When Google appeared on my radar in late 1999/early 2000, it was a revelation. For the first time in many years, I could enter a search term and have a 75% chance of success compared to sub-50% rate of other search engines. The gap in effectiveness was too large for any other search engine to bridge.

(This also sort-of explains why Bing will have a hard time unseating Google. Google has improved to about 95% accuracy for me. Even if Bing gets to 99.9% accuracy, I probably wouldn't notice the difference.)