Really, it wasn't that much better, at least not to me at the time. I'd switch search engines every few months, or more accurately have 3 or 4 search engines to deploy against difficult queries.
Google was _slightly_ better than alltheweb.com at the time that I added it into the mix. But it slowly began to win more and more of the "query requires using 4 search engines" contests and eventually I only used one.
It was better, but I can't remember thinking it wasn't orders of magnitude better. I didn't use it once and think 'oh my god, this is perfect'. It was a gradual switch. And to begin with the thing which made me use it more was the simple UI.