It wasn't just about interface. People tend to forget how search engines did an absolutely horrible job of intelligently ranking the sites you wanted to see. They relied primarily upon keywords and other sort of fairly obvious metrics on the site itself, which of course can be significantly gamed. I've seen "tag clouds" on some sites and blogs, which I'm presuming is due in part to one of the historical metrics being how large a visible word is on a site - the obvious presumption being that keywords in titles should be weighted more heavily.
Google showed up and not only provided a vastly superior interface (look, all you want is to search, right? Here you go!), it also was the very first search engine that actually had a really good chance at returning the most relevant search as the very first result due to it's PageRank algorithm - hence, the "I'm feeling lucky!" button. Such a button would have been labelled "I'd love to win the lottery!" for other search engines, since the results you were looking for might well be on page 13 of a hundred pages of results returned.
One could argue that although Google did not invent web searching, they may have been the first ones to invent truly effective web searching algorithms. It was only the pressure of Google's overwhelming effectiveness that forced other companies to significantly improve their own search engines. Even today, other companies have a hard time even reaching parity with Google search, let alone exceeding it, although such metrics are obviously somewhat subjective.