In the beginning, what was revolutionary about Google was the experience, not the search results. A lot of that has to do with visual design. But mostly, in Google's case, I think it has to do with the extreme focus they have on search.
I think it was a combination of:
* A better search algorithm than the competition
* Lack of paid-for search rankings, which were common-place previous to Google
* Tasteful, lightweight, fast design with a lack of intrusive banner ads
All 3 are largely taken for granted these days.
The one reason I switched to google was because on the search engine I was using the search results and images took a really long time to load on a 56k modem, while google's results page loaded instantaneously.
Google's search engine wasn't revolutionary either. It was only moderately better than AltaVista and others. Most of all the visual design was cleaner. Google's main accomplishment was imo the introduction of AdSense.