People switched to Google because it had a nice clean white page with a single search box, while AltaVista was going the 90s fad portal route. Clean interface and simplicity was thee key,
There's lots of talk about how Google's search algos were better than AltaVista but honestly, at first, they weren't. They were close and they improved, but the loading speed and simplicity advantage that Google had over AltaVista is what bought them time to improve. Remember too that one reason AltaVista was better was that people optimised to be found by it, and not for Google. As time went on, more people learned what Page Rank was (long since gone) and started to optimise for that instead, thus speeding up the switch.
Lesson: Don't go complex. Don't go shoving extra stuff at people that they haven't asked for. Give them the simplest thing possible, and they will use it.