I think at least at first, Google's success was definitely because of the algorithm. Existing search engines were terrible. They primarily relied on text analysis and human edited web directories. You could search for something as basic as "pet food" and get a few relevant results and then a bunch of random garbage. When Google came out using PageRank, it was a whole new world. Every tech savvy person I know switched right away, and not because of the interface.

But no doubt the simple and elegant interface helped too, and has helped them stay ahead as the other search engines have caught up with their algorithm.