$\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 s', the value function for $\pi$,
$$v_{\pi}(s') <v_{\pi_{0}'}(s')\leq v_{\pi_{1}'}(s')\leq v_{\pi_{2}'}(s') \leq ...\leq v_{\pi_{\infty}'}(s')\tag{3}$$
for $s\in{S/\{s'\}}$, the value function for $\pi$,
$$v_{\pi}(s) \leq v_{\pi_{0}'}(s)\leq v_{\pi_{1}'}(s)\leq v_{\pi_{2}'}(s) \leq ...\leq v_{\pi_{\infty}'}(s)\tag{4}$$
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 (3) and (4).
For example, ${Let}\space { a' }=\arg \max_{a\in A} q_\pi(s',a)$.
For $s_0=s'$, $$\align{v_{\pi}(s_0) &< \max_{a\in A} q_\pi(s',a)\\&=v_{\pi_0'}(s')\\&= q_\pi(s',a')\\&=E_{s_1\in S}[r(s',a',s_1)+ \lambda v_{\pi}(s_1)]\\&=E_{s_1\in S}[r(s',a',s_1)+ \lambda E_{a_1\in A}[q_\pi(s_1,a_1)]]\\&=E_{s_1\in S/\{s'\}}[r(s',a',s_1)+ \lambda E_{a_1\in A}[q_\pi(s_1,a_1)]]+E_{s'}[r(s',a',s')+\lambda E_{a_1\in A}[q_\pi(s',a_1)]]\\&\leq E_{s_1\in S/\{s'\}}[r(s',a',s_1)+ \lambda E_{a_1\in A}[q_\pi(s_1,a_1)]]+E_{s'}[r(s',a',s')+\lambda \max_{a\in A}q_\pi(s',a)]\\&=v_{\pi_1'}(s')}\tag{5}$$
For $s_0\in$ S/{s'}, $$\align{v_{\pi}(s_0) &= E_{a_0\in A}[q_\pi(s_0,a_0)]\\&=v_{\pi_0'}(s_0)\\&=E_{a_0\in A}[E_{s_1\in S}[r(s_0,a_0,s_1)+ \lambda v_{\pi}(s_1)]]\\&=E_{a_0\in A}[E_{s_1\in S}[r(s_0,a_0,s_1)+ \lambda E_{a_1\in A}[q_\pi(s_1,a_1)]]]\\&=E_{a_0\in A}[E_{s_1\in S/\{s'\}}[r(s_0,a_0,s_1)+ \lambda E_{a_1\in A}[q_\pi(s_1,a_1)]]]+E_{a_0\in A}[E_{s'}[r(s_0,a_0,s')+ \lambda E_{a_1\in A}[q_\pi(s',a_1)]]]\\&\leq E_{a_0\in A}[E_{s_1\in S/\{s'\}}[r(s_0,a_0,s_1)+ \lambda E_{a_1\in A}[q_\pi(s_1,a_1)]]]+E_{a_0\in A}[E_{s'}[r(s_0,a_0,s')+ \lambda \max_{a\in A}q_\pi(s',a)]]\\&=v_{\pi_1'}(s_0)}\tag{6}$$
I want to make it clear thus the rather complex notations. Note that the difference between the strictly less than symbol and the less than symbol in (5) and (6). This is because the probability to replace $v_{\pi}(s')$ with a bigger $\max_{a\in A} q_{\pi}(s',a)$ might be zero.
We can approximate $v_{\pi_{\infty}'}(s)$ naively, pretty much as what we do in (5) and (6), by expanding the equation to t=t' that is big enough that the remainder would be negligible w.r.t our strictly less than inequality, that is $v_{\pi_{\infty}'}^{approx}(s') > v_{\pi}(s')$, and $v_{\pi_{\infty}'}^{approx}(s) > v_{\pi}(s)$ for $s\in S/\{s'\}$ if $v_{\pi_{\infty}'}(s) > v_{\pi}(s)$, and we let $v_{\pi_{\infty}'}^{approx}(s) = v_{\pi}(s)$ for the rest. And because $v_{\pi'}(s) \geq v_{\pi_{\infty}'}^{approx}(s)$ is also true for all $s\in S$. We get that $v_{\pi'}(s) >v_{\pi}(s)$ for $s\in S$ if $v_{\pi_{\infty}'}(s) > v_{\pi}(s)$, and $v_{\pi'}(s) \geq v_{\pi}(s)$ for the others. Thus, $\pi'$ is indeed a strictly 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.