Complexity lower bound for regular languages
I'll answer my own question -- the conjectured lower bound is false. Consider 
$L_n=\Sigma^* 0 \Sigma^n$ (that is, the collection of all strings with a $0$ in the $n$th location from the end). It's easy to see that there is an $O(n)$ size NFA for $L_n$, but the minimal DFA for $L_n$ is exponential. Here is a TM that decides membership in $L_n$ in time $O(|x|+n)$: scan $x$ to the end (time $|x|$) and read $n$ steps back to see if that letter is $0$.