Если создавать Random в одно время, то они будут инициироваться одним и тем же числом. Настоящая генерация псевдослучайных чисел происходит при вызове метода Next и должна вызываться у одного и того же объекта Random.
Создайте один раз Random, инициировав его, например, количеством тиков: new Random((int) DateTime.Now.Ticks & 0x0000FFFF).
Конструктор Random (Int32)
Затем используйте Next(), для получения следующих чисел.