На самом деле
Task.WhenAll тоже не стартует все таски параллельно, таски исполняются в
ThreadPool и именно он отвечает за запуск тасков. Если вам нужно ограничить параллельность сверху то можно использовать подобное решение:
MSDN
Каким образом вы выясняли, что 500 задач оптимальный вариант?
Между тем Windows оперирует потоками и чем больше потоков запущено, тем больше времени уходит на переключение между ними.