$\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}
$$
We break any tie in $\arg\max$ arbitrarily. 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}$$

Note 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$.

We can also get other properties from this proof:(1) a very similar proof, slight modification is probably required, would shows that we only need to take into account deterministic policies, that is, for any stochastic policy we can always find a deterministic policy that is at least as good as the stochastic policy. (2)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 if there are multiple optimal policies, or worse than the policy $\pi$ by showing $\pi$ is better than all other policies using the same proof but replacing all bigger than operators with smaller than operators. (3)We can also show the existence of an optimal policy in finite MDP by the above proof. Because we only need to take into account deterministic policies and they are finite, we can continuously updating our policy using the above proof. Before we go over all possibilities, we would come upon a policy $\pi$ that satisfies $v_{\pi}(s)=\max_{a\in A} q_{\pi}(s,a)$ for all $s\in S$ because a policy cannot show up twice while we are updating our policy or it will be strictly better and strictly worse than policies in between at the same time.