Two orders of magnitude is a serious exaggeration. I remember swapping back and forth through multiple search engines well after Google showed up. Search index size and update frequency used to be a much larger issue for me.
Early on I swapped from yahoo mail to gmail to hotmail because gmails spam filtering wasn’t good enough. Among my fiends Gmail really won on UI not space.