Do there exist any problems with optimal algorithms beyond $O(n)$?
(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).