As I recall, Altavista and Lycos tended to prove the most useful for me in the pre-Google era. Yahoo was hit or miss and Excite was middling.
I’d bet that the things being searched for influenced which engines were best for a given individual. It’s too bad there’s no way to see what each excelled at.