I remember using Altavista, Excite, WebCrawler and Yahoo simultaneously in order to find what I wanted.
One day, I decided to try Google. I remember having thought "Humm, this seems to be slightly better. I'll use it for a while"
Sometimes it seems incredible that it was only 10 years ago.
Additional note that most other search engines were a test of pain before Google came along.