$\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 stochastic 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\begin{cases} 1&if \space s=s' and \space a=\arg \max_{a\in A} q_\pi(s',a)\\ 0&if \space s=s' and\space a\neq\arg \max_{a\in A} q_\pi(s',a)\\ {\pi}&if\space s \in S/\{s'\} \end{cases}\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\begin{cases} 1&if \space s=s' and\space a=\arg \max_{a\in A} q_\pi(s',a)\space and\space T\leq t\\ 0&if\space s=s' and\space a\neq\arg \max_{a\in A} q_\pi(s',a)\space and\space T\leq t\\ {\pi}&else \end{cases}\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.
We can also get other properties from this proof. For example, it also shows that we only need to take into account deterministic policies because for any stochastic policy the above derivation tell us we can always find a deterministic policy that is at least as good as the stochastic policy. Another interesting consequence results from this proof is that if a policy $\pi$ satisfy $v_{\pi}(s)=\max_{a\in A} q_{\pi}(s,a)$ for all $s\in S$ then we can say that it is an optimal policy because we can prove that all other policies are only as good or worse than the policy $\pi$ by replacing all the smaller than operator with a bigger than operator in the proof and prove it in a similar way. Sadly, I am not sure whether it can be used to prove the existence of an optimal policy though it seems that all value function has to converge to a value after a certain number of updates using this method, for the rewards are usually bounded.