I think set items should be side stories, not just random. I got sick of finding only two pieces of every set in Diablo II. Each set suits a particular class or cross-class.
They don't have to be big stories, just "I heard there is this magical armour of the Frost Giant over there..." and "Did you hear about the Frost Giant's club?" I was also annoyed that the sets were named after people I'd never heard of and could ask about.
