$\newcommand{\align}[1]{\begin{align*}#1\end{align*}}$I had just the same question while learning RL these few days. I think the derivation on pages 31 and 32 in slides from https://www.cs.cmu.edu/~mgormley/courses/10601-s17/slides/lecture26-ri.pdf kind of gives us an intuition why $v_{\pi^{*}}(s)=\max_{a\in A} q_{\pi^*}(s,a)$ for all $s\in S$. Though the slides consider the case where ${\pi}$ is deterministic, it can be applied to the undeterministic case $\pi(a|s)$. If there is any mistake below, please point it out.
If $\exists{s'}\in{S}$ such that a value function $v_\pi(s')< \max_{a\in A} q_\pi(s',a)$ then we can define a new policy $$ {\pi'}\equiv\cases{1&if s=s' and $a=\arg \max_{a\in A} q_\pi(s',a)$\\0&if s=s' and $a\neq\arg \max_{a\in A} q_\pi(s',a)$\\{\pi}&if s $\in$S/{s'}}\tag{1} $$ now we want to prove that $\pi'$ is a better policy than $\pi$ by using a recursive method similar to the one in the above slides.
define a notation $$ {\pi_{t}'}\equiv\cases{1&if s=s' and $a=\arg \max_{a\in A}$ $q_\pi(s',a)$ and $T\leq t$\\0&if s=s' and $a\neq\arg \max_{a\in A} q_\pi(s',a)$ and $ T\leq t$\\{\pi}&else}\tag{2} $$
for $\forall s\in{S}$, the value function for $\pi$,
$$v_{\pi}(s) <v_{\pi_{0}'}(s)<v_{\pi_{1}'}(s)<v_{\pi_{2}'}(s)<...<v_{\pi_{\infty}'}(s)\tag{3}$$ the above inequality is true because we are simply replacing $v_{\pi}(s')$ with a bigger $\max_{a\in A} q_{\pi}(s',a)$ when calculating the value functions in (1). For example,
$$\align{v_{\pi}(s') &< \max_{a\in A} q_\pi(s',a)\\&=v_{\pi_0'}(s')\\&=E_{s\in S}[r(s',a,s)+ \lambda v_{\pi}(s)]\\&=E_{s\in S/\{s'\}}[r(s',a,s)+ \lambda v_{\pi}(s)]+E_{s'}[r(s',r,s')+\lambda v_{\pi}(s')]\\&< E_{s\in S/\{s'\}}[r(s',a,s)+ \lambda v_{\pi}(s)]+E_{s'}[r(s',r,s')+\lambda \max_{a\in A}q_\pi(s',a)]\\&=v_{\pi_1'}(s')}$$
We can approximate $v_{\pi_{\infty}'}(s)$ naively by expanding the equation to t=t' that is big enough that the remainder would be negligible w.r.t our inequality, that is $v_{\pi_{\infty}'}^{approx}(s) > v_{\pi}(s)$ for all $s\in S$. And because $v_{\pi'}(s) > v_{\pi_{\infty}'}^{approx}(s)$ also for all $s\in S$. We get that $v_{\pi'}(s) >v_{\pi}(s)$ for all $s\in S$, thus, $\pi'$ is indeed a better policy than $\pi$.
The above derivation is true for all policy $\pi$, thus it is also true for an optimal policy $\pi^*$ if it exists.
So, together with $v_{\pi^*}(s) \leq \max_{a\in A}q_{\pi^*}(s,a)$ for all $s\in S$ and the proof by contradiction provided by other answers. We can conclude that if there exists an optimal policy $\pi^*$, then $v_{\pi^{*}}(s)=\max_{a\in A} q_{\pi^*}(s,a)$ for all $s\in S$ and there will also exist an optimal policy $\pi^{**}$ that is deterministic.