From memory - and this was a long time ago so my memory is almost certainly wrong - I used Altavista for general searching with Yahoo's human-edited indexes when Altavista wasn't good enough, and then switched to using Google for general searching with Yahoo's human-edited indexes when Google wasn't good enough.
That's how I remember it too: Altavista was the best for searches, partly because it understood boolean words like AND and OR and grouping with parentheses. That was great for when you weren't sure which of a few different words or spellings people might use. Can any search engine today do something like "(linux OR unix) AND (kernel OR kernal)", without breaking it up into various fields in an Advanced Search form? Then if AV couldn't find anything, I'd start digging through directories like Yahoo. Seems like there was a stretch where I used Lycos for search too, but I can't remember if that was pre- or post- Altavista.
iirc, I was using Lycos (briefly) before AltaVista. I remember using Yahoo for general searching as well; the only human-curated database I remember using to any extent was the Netscape one, now known as Open Directory.