Выбрать из списка 400 случайных элементов

На первый взгляд, это классическая задача на алгоритм Reservoir Sampling. Задача решается за один последовательный проход по списку, и при этом для достижения равновероятной выборки вам даже не надо заранее знать количества элементов в списке. При этом не нужно прибегать к ужасной порочной практике "проб и ошибок" (проверка "уже брали - еще не брали"), которую часто предлагают использовать при составлении наивных алгоритмов для решения данной задачи.

Алгоритм таков:

1. Заводим массив из 400 элементов и заполняем его первыми 400 элементами списка.

2. Читаем в цикле дальнейшие элементы списка (с 401-го и далее):

   2.1. Берем i-тый элемент из списка и с вероятностью 400/i принимаем решение сохранить этот элемент в нашей выборке. Если принято решение "не сохранять", то просто пропускаем его.

   2.2. Если принято решение сохранить элемент, сохраняем его в случайную позицию в нашем массиве (выбросив оттуда предыдущий элемент).

Пройдя таким циклом весь список до конца, мы получим 400 равновероятно выбранных элементов списка.

Как видите, для эффективной реализации выбранные 400 элементов желательно в процессе работы алгоритма хранить в массиве, а не в списке. Тут уже думайте сами, как лучше поступить: завести изначально массив, а затем скопировать выбранные элементы в список, или сразу хранить их в списке, пожертвовав эффективностью прямого доступа при замене на шаге 2.2.

Однако если ваш исходный список предоставляет возможность эффективного прямого доступа (см. комментарий @Андрей NOP), то вариант "проб и ошибок" будет вполне жизнеспособным и даже более эффективным, так как 400 намного меньше 10000.

Если производительность некритична перемешиваем весь список

Неоптимальный и грубый, но достаточно прямолинейный подход: перемешать весь список в случайном порядке и выбрать первые 400:

var random = new Random();
var listNew = list.OrderBy(s=> random.Next()).Take(400).ToList();

Неоптимальный т.к. будет сортировать весь список.
Грубый т.к. коллизии случайных чисел приведут к тому, что попадание первых по порядку элементов будет на какую долю выше.

Поход для малой выборки: отбираем уникальные индексы

Напишем метод, который генерирует бесконечную последовательность случайных индексов:

private static Random random;
public static IEnumerable<int> RandomNumbers(int maxValue)
    {
        while (true)
        {
            yield return random.Next(maxValue);
        }
    } 

С помощью метода получим 400 уникальных индексов и отберем элементы:

var uniqueIndices = RandomNumbers(list.Count).Distinct().Take(400);
var listNew = uniqueIndices.Select(i => list[i]).ToList();

Недостаток этого подхода в то что он подходит только для выбора малого (по сравнению с размером исходной выборки) количества элементов. Если Вам потребуется отобрать 9999 элементов, этот метод будет неоптимален ввиду частых совпадений случайных чисел.