Что ж, вы можете создать один одномерный массив, заполнить его, а затем скопировать его с помощью Buffer.BlockCopy:
Random random = new Random();
byte[] row = new byte[size * size];
random.NextBytes(row);
Buffer.BlockCopy(row, 0, fullMap, 0, size * size);
Однако, прежде чем пытаться оптимизировать еще больше - насколько быстро выэто должно быть?Вы протестировали приложение и определили, что это узкое место вашего приложения?