Here's my attempt at an intuitive explanation of the fact that $u_1$ and $u_2$ are guaranteed to be orthogonal, based on the answer given by @user1952009.
Throughout this answer, $\| \cdot \|$ will denote the $\ell_2$-norm.
Assume that $v_1$ is a maximizer of $\|Av\|$ subject to the constraint that $\|v\| = 1$. Assume also that $v_2 \perp v_1$.
Claim: Under these assumptions, $A v_2 \perp A v_1$.
Explanation:
It's possible to look at this in a way that makes it intuitive or even "obvious". If $Av_2$ were not orthogonal to $A v_1$, then it seems like we could improve $v_1$ by adding $\epsilon v_2$ to it, for a sufficiently tiny value of $\epsilon$. When we perturb $v_1$ a tiny bit in the direction of $v_2$, then the norm of $v_1$ does not change (to first order, at least). [A satellite in circular orbit moves locally in a straight line, and its distance from the center of the Earth is constant.]
However, we cannot say the same for the norm of $Av_1$, because $A v_1$ is perturbed in the direction of $A v_2$, and $A v_1$ and $A v_2$ are not orthogonal. The growth in $\| A v_1 \|$ is non-negligible.
Again: when $v_1$ is perturbed in the direction $v_2$, the change in norm is negligible (so the norm is still $1$). But, $A v_1$ is perturbed in the direction $A v_2$, and the change in norm is non-negligible (so the norm can increase).
Suppose you're standing 1 kilometer from the origin and you want to take a step in order to increase the magnitude of your displacement vector from the origin. In which direction should you move? Is it better to move in a direction orthogonal to your displacement vector, or parallel to it? If you step in a direction orthogonal to your displacement vector, then the change in the magnitude of your displacement vector is negligible. However, if you step in a direction parallel to your displacement vector, then the change in magnitude of your displacement vector is significant.
Finally, let's convert this intuition into a rigorous proof.
To get a rigorous proof, we have to face the fact that
$v_1 + \epsilon v_2$ does not actually have norm $1$ when $\epsilon \neq 0$,
even if $\epsilon$ is tiny.
We can fix this by taking our perturbed version of $v_1$ to be
\begin{equation}
\tag{$\spadesuit$} \tilde v(\epsilon) = \sqrt{1 - \epsilon^2} \, v_1 + \epsilon v_2.
\end{equation}
The vector $\tilde v(\epsilon)$ really does have norm $1$.
We are assuming (for a contradiction) that
$A v_2$ is not orthogonal to $A v_1$. This implies
that $A v_2 = c A v_1 + w$, for some $c \neq 0$
and $w \perp A v_1$.
It follows that
\begin{align}
\| A \tilde v(\epsilon) \|_2^2 &= \| (\sqrt{1 - \epsilon^2} + c \epsilon) A v_1 + \epsilon w \|^2 \\
&= (\underbrace{\sqrt{1 - \epsilon^2} + c \epsilon}_{>1 \text{ if }\epsilon \text{ is small enough}})^2 \| A v_1 \|^2 + \epsilon^2 \| w \|^2.
\end{align}
This shows that $v_1$ is not a true maximizer of $\| A v \|$ subject to the constraint $\| v\|_1$. We have arrived at a contradiction.
The point of the intuitive discussion was to explain how we might think of perturbing $v_1$ as in equation ($\spadesuit$), and why we would expect this perturbation of $v_1$ to be an improvement on $v_1$.