No, this is not true in general.

Note that in your condition you probably want to assume $\|u\|=1$ for otherwise you could always make the left hand side as small as you wish by making $u$ small. I will answer the question for the Euclidean norm and the induced spectral norm but this does not really make a huge difference.

Aassuming $\|u\|=1$, all that we learn from the condition is that $(A-\lambda I)u = y$ with $\|y\| < \varepsilon$. This can be rewritten to say
$$ (A - yu^T)u = \lambda  u$$
so that a perturbation of $A$ of size less than $\varepsilon$ moves one eigenvalue to the imaginary axis. Note that $\| yu^T\|=\|y\|$.

Now as you suspect, for nonnormal matrices perturbations of size $\varepsilon$ can have significant effects on the spectrum and there is no reason to assume that the effect is itself bounded by $\varepsilon$. To get more information you need to know more about $A$ and possibly about the type of perturbations that are of interest. There is a wealth of literature on this. As you are from engineering I suggest to read up on the concepts stability radii, spectral value sets and some of the introductory papers by Trefethen.

A small comment aside: you say that "we engineers say $\lambda$ is in the $\varepsilon$-pseudospectrum of $A$"; historically the term was first coined by mathematicians.