Это не будет генерировать SQL-запрос, который вы просматриваете, но должен возвращать случайный результат без необходимости извлечения всех записей:
Random r = new Random();
var record = r.Next(Advertising.Count());
var randomRecord = Advertising.Skip(record).FirstOrDefault(1);
Редактировать: он также должен быть более эффективным, чем случайная сортировка(если только SQL Server не оптимизирует сортировку)
Редактировать 2: Take (1) должно быть FirstOrDefault () для возврата записи, а не записи из списка 1 длиной.