Does the time it take you to finish her quest a factor in what kind of prize she gives you? Or is the prize just completely random? I keep getting junk...

She gives you a Shinwa item which is completely random.

Alright thanks. I guess it's kind of a luck thing then, Sagg's quests make up for my bad Shinwa days though =)

Maleria sometimes gives great things. She can get pricey though, but then the other two do as well.