Зачем оператор new в C#?
Объяснение для новичка с углублением с CLR.
Такой синтаксис придумали использовать в C# для вызова конструктора.
Конструктор после компиляции - это метод с именем ".ctor" — из-за этого его нельзя просто-так руками объявить или вызвать.
Есть язык F#, в котором конструктор вызывается без new — на нём бы ваш пример выглядел так:
a[Random().Next(0, a.Length)]
Конструкторы нужны чтобы инициализировать экземпляры объектов.

Я бы посоветовал вам вынести Random в новую переменную, чтобы не пересоздавать его каждый раз, когда вы хотите вытащить случайный элемент массива.
Оператор new создаёт экземпляр типа. 

В данном случае тип (класс) Random. Чтобы создать объект (т.е. экземпляр) этого типа, нужно к этому типу применить оператор new. 
Вызов конструктора и инициализация полей объекта происходит после создания экземпляра. C# позволяет при создании экземпляра типа указать "функцию" - конструктор (у типа их может быть несколько) - чтобы инициализировать созданный объект сразу же после создания. 

Зачем вообще нужен экземпляр типа? Опять же на примере вашего кода -  вы хотите использовать метод Next для получения следующего случайного числа. Алгоритм расчета псевдослучайного числа всегда работает с использованием какого-то начального значения, при создании экземпляра типа это значение инициализируется и хранится в конкретно этом экземпляре типа. 

Ссылки по теме. 
https://docs.microsoft.com/en-us/dotnet/csharp/lan...
https://docs.microsoft.com/en-us/dotnet/csharp/lan...