Is it possible to solve the halting-after-$n$ steps problem more efficient than just execute $n$ steps?
The time hierarchy theorem, or rather its proof, gives some answer to this question. If you look at the proof, you should get a lower bound of $\Omega(n/\log n)$.

In more detail, consider the language $L$ of all triples $\langle M,x,1^t \rangle$ such that $M$ halts on $x$ after at most $t$ steps. Suppose that this can be solved in time $f(n)$, where $n$ is the input length (which is $t + |M| + |x|$). Then you can construct a Turing machine which on input $\langle x,1^t \rangle$ determines whether $\langle x,x,1^t \rangle \in L$, if so runs into an infinite loop, otherwise halts. When run on itself as input, this machine either halts in time $f(t + O(1)) + O(1)$ or never halts. Hence if $f(t + O(1)) + O(1) \leq t$, we reach a contradiction. This shows that $f$ has to essentially be at list linear.