Eigenvalues of normal matrices move by at most the size of the perturbation

First statement. By the spectral theorem for normal matrices, $A=UDU^*$ with $U$ unitary and $D$ diagonal. Then $\|U\|=\|U^{-1}\|=1$, so $\kappa(U)=1$. Bauer-Fike gives
$$\min_i|\mu-d_i|\le\kappa(U)\|E\|=\|E\|.$$

Symmetric case, sorted eigenvalues (Weyl). For real symmetric $A$ with eigenvalues $\lambda_1\le\dots\le\lambda_n$, the Courant-Fischer formula says
$$\lambda_k(A)=\min_{\dim V=k}\ \max_{x\in V,|x|=1}x^TAx.$$
For a unit $x$, $x^T(A+E)x\le x^TAx+\|E\|$, hence $\lambda_k(A+E)\le\lambda_k(A)+\|E\|$. Applying this to the pair $(A+E,-E)$ gives $\lambda_k(A)\le\lambda_k(A+E)+\|E\|$. So
$$|\lambda_k(A+E)-\lambda_k(A)|\le\|E\|.$$

Example. $A=\operatorname{diag}(1,3)$ and $E=\begin{pmatrix}0&\varepsilon\\\varepsilon&0\end{pmatrix}$ with $\|E\|=\varepsilon$: the eigenvalues of $A+E$ are $2\pm\sqrt{1+\varepsilon^2}$, which differ from $1,3$ by $\sqrt{1+\varepsilon^2}-1\le\varepsilon^2/2<\varepsilon$.

Remark. The contrast with the nilpotent Jordan block (change $\varepsilon^{1/n}$ for a perturbation of size $\varepsilon$) shows that non-normality is exactly what makes eigenvalues sensitive. This also explains why symmetric eigenproblems are numerically much easier than general ones.