> I've tried seeding it each time with Time.now.usec, but that 
> seems to make 
> it worse (which makes sense, because it probably takes less than a micro 
> second between each generation).
> 
> Any suggestions?

Call srand once, or don't call it at all.