Google was a huge improvement because if you searched for Foo Bar Baz it would only give you pages that had all the words Foo, Bar and Baz whereas AltaVista et al. would give you pages containing any of the words, if memory serves. But the speed was a huge deal too, especially on a 56k modem (and the thing had to be rendered in IE4 on a Pentium II too, let's not forget).