In various ML talks I keep hearing that variance estimation is harder than mean estimation but I never really get why the above statement is correct. Is there a theoretical argument or a published analysis on this which backs this claim?
Yes, it is basically TRUE.
Mean is a first moment, the variance a second moment. Assuming moment estimates, the variance of an empirical mean is a second moment. The variance of an empirical variance is a fourth moment. So to ascertain the uncertainty in a variance estimate, you take fourth powers of your data! That will end to magnify errors quite a bit ...
That shows up --- mean estimates have some robustness properties, variance estimates not so much. So inference about variances tend to depend much more on underlying assumptions than do inferences on means. (I will add to this later)