First of all I have to express my opinion that the gap between large sample behavior and the finite sample behavior should be considered "unsurprising".
Basically speaking, the theory of asymptotics using the framework of decision theory is much tougher than most mathematicians think nowadays if they ever read into [Le Cam]'s exposition. This kind of difficulty mostly arise from two sources, from my perspective. The first one is the typical difficulty in determination of loss function, convexity is convenient yet concavity is a more faithful description of boundary behavior (when sequence of rules tends to $\infty$, in most cases we consider the rules indexed by sample sizes $n$.), this flaws are very carefully(probably over-carefully discussed in pp.16-23 of [Le Cam]). The second one is closer to what you think in OP, that is the inconsistency between local and global asymptotic behaviors, which is also discussed in Chap.10-11 of [Le Cam]. This problem is becoming more and more central concern in recent research, you may also want to read my post Is there a result that provides the bootstrap is valid if and only if the statistic is smooth?, which explained why sometimes seemingly unnecessary "linearity conditions" will be imposed on some asymptotic results.
Although I do not quite agree with your opinion, this question is actually quite interesting, therefore I want to focus on a more specific version of the problem you raise, and then return to your question that "What are some other surprising results of finite sample statistics?" We firstly considered the small sample approximation, and then a correction and discussion about your observation: the different between small/finite sample behavior and large/asymptotic behavior.
Thank you for sharing your thoughts!
$\blacksquare$1.The introduction of small sample asymptotics.
If you are concerned with the asymptotic behavior of finite sample, a relevant field of research that is called "small sample asymptotics" [Field&Ronchetti]. This field has at least two motivations, one is mentioned in [Field&Ronchetti] Preface:
"...The central question is that of finding good approximations to the
density of statistics in situations where the computation of the exact
density is intractable.... The small sample approximations are simpler
than Edgeworth expansion and can be thought of as a series of low
order Edgeworth expansions. We obtain much better numerical accuracy
than the Edgeworth and our density approximations are always positive
unlike the Edgeworth. "
The other is actually the demanding need of studying the robustness of certain estimators(M-estimators). When an accurate approximation is available, we do not have to worry about multiple Hadamard differentiation when studying the influence of certain observations. Huber and Ronchetti even updated this contribution into Huber's epic work [Huber] when revised.
Both motivations are kind of vanishing a bit nowadays, the numerical concern is not so central as computation resource is growing; the study of robustness is actually not so popular, mostly due to the rise of MCMC about the same time after Huber's Princeton Robust seminar.
$\blacksquare$2.About random matrix asymptotics.
You said in OP that:
Many results on random matrices have very similar results in the
finite sample and asymptotic regimes. For example, bounds on the
minimum and maximum eigenvalues of random matrices are comparable in
both regimes.
This is completely not true. If you view random matrices as sort of representation of the transition kernel topological group, or equivalently dependent stochastic processes, then there are so many discrepancies between asymptotic bound and concentration bound mentioned in [Talagrand]. Things like Berry–Esseen bound(since you talked about empirical mean) is more like a coincidence rather than a universal fact. And the concentration bound is usually looser than asymptotic counterparts, and come with more restrictions.
What [Devroye] showed is a concentration bound (a bound that holds with high probability). This is not uncommon in mathematics, say subharmonic functions sequence do not always converge to subharmonic functions, how can we expect that a subharmonic estimator(empirical mean) sequence converges to a harmonic limit(Gaussian when taking $n\rightarrow \infty$)?
More obviously for finite sample you always have union bound, how about that asymptotically?
$\blacksquare$3.What are some other surprising results of finite sample statistics?
There are quite a few examples that concentration bound disagrees with asymptotic bound as I mentioned above shown in [Talagrand] and [Le Cam]Chap 10-11. But the most famous example that fits your description should be the order statistics from extreme value theory, its asymptotic distribution is exponential (Limiting distribution of the first order statistic of a general distribution) while the distribution of finite sample order statistics $(X_{(1)},\cdots,X_{(n)})$ always depends on the underlying distribution itself. Not surprisingly the Efron-Stein concentration bound is much looser in this case. So what I said is that such disagreement between concentration bound and asymptotic bound is rather common.
Reference
[Le Cam]Le Cam, Lucien. Asymptotic methods in statistical decision theory. Springer Science & Business Media, 2012.
[Field&Ronchetti]Field, Christopher A., and Elvezio Ronchetti. "Small sample asymptotics." Ims, 1990.
[Huber&Ronchetti]Huber, Peter J. Robust statistics. Springer Berlin Heidelberg, 2011.
[Devroye]Devroye, Luc, et al. "Sub-Gaussian mean estimators." The Annals of Statistics 44.6 (2016): 2695-2725.
[Talagrand]Talagrand, Michel. The generic chaining: upper and lower bounds of stochastic processes. Springer Science & Business Media, 2006.
[Hayman2]Hayman, Walter Kurt. Subharmonic functions. Vol. 2. Elsevier, 2014.
