Here is a partial answer. But let me first modify the question by replacing the reals by the complex. Hence, $x$ runs over ${\mathbb C}^n$ and $A_1,A_2$ are Hermitian. Then $A_1,A_2$ can be viewed as the "real" and "imaginary" parts of a single matrix $M=A_1+iA_2$, that is
$$A_1=\frac12(M+M^*),\qquad A_2=\frac1{2i}(M-M^*).$$
The advantage of working within the complex numbers is that we know (Toeplitz-Hausdorff Theorem) that the image ${\cal H}(M)$ of the unit sphere of ${\mathbb C}^n$ under the numerical map $x\mapsto x^*Mx=x^*A_1x+ix^*A_2x$ is a convex compact subset of the complex plane.

Now, $\lambda_\min(A_1,A_2)$ (under the complex definition) is the minimum of the convex function $f(z)=\max(\Re z,\Im z)$ over ${\cal H}(M)$. We easily see that it is achieved on the boundary of ${\cal H}(M)$, at a point which is either the downmost point, or the leftmost point, or the most SW point along the diagonal $\Delta$ defined by $\Re z=\Im z$.

Specifically, we have the following alternative, where $x$ (resp. $y$) denotes some unit eigenvector of $A_1$ (resp. $A_2$) associated with $\lambda_\min(A_1)$ (resp. $\lambda_\min(A_2)$) :

- either $x^*A_1x>x^*A_2x$, and then $\lambda_\min(A_1,A_2)= \lambda_\min(A_1)$,
- or $y^*A_2y>y^*A_1y$, and then $\lambda_\min(A_1,A_2)= \lambda_\min(A_2)$,
- or $x^*A_1x\le x^*A_2x$
**and** $y^*A_2y\le y^*A_1y$, and then $t:=\lambda_\min(A_1,A_2)$ is the number such that $(t,t)$ is the down-left point of the interval ${\cal H}(M)\cap\Delta$.