Do there exist any problems with optimal algorithms beyond $O(n)$? Blum's Speedup Theorem famously shows that there are problems which admit no fastest algorithm. This raises an obvious question: are there any problems that do admit a fastest algorithm? In other words, does there exist a language $L$ which is decided by some algorithm within $f(n)$ steps so that any other algorithm which solves the same problem also runs in $\Omega(f(n))$ steps? If $f$ is linear, this is trivially the case. But what about beyond linear? Just a nonconstructive existence proof would already be cool.
(Deterministic) TMs with a single tape can recognize palindromes in time $O(n^2)$. It has been proven that this time bound is optimal (see, e.g., this paper).

Also, the time hierarchy theorems give you an endless supply of such examples (though they are not natural problems, of course).