Данные по времени выполнения задачи сильно скошены и имеют длинный хвост. Какое утверждение наиболее корректно про нормальное приближение для выборочного среднего при росте размера выборки?

Когда вы берёте выборочное среднее по многим наблюдениям, вы фактически суммируете много вкладов и делите на размер выборки. Это и приводит к нормальному приближению распределения оценки среднего, даже если исходные значения асимметричны. Но при небольшом размере выборки и сильных выбросах приближение может быть хуже. LLN говорит про сходимость самого среднего к матожиданию, а не про форму распределения исходных данных.