A solução para isso é utilizar o método Sleep para dar um tempo de 3 milisegundos entre a criação de cada uma das instâncias dos objetos Randon, ou utilizar o mesmo objeto para gerar o outro número.
Random r1 = new Random();
Random r2 = new Random();
int a1 = r1.Next();
int a2 = r2.Next();
As variáveis a1 e a2 terão o mesmo valor.
Random r1 = new Random();
System.Threading.Thread.Sleep(3);
Random r2 = new Random();
int a1 = r1.Next();
int a2 = r2.Next();