Here's a geometrical reformulation of the problem that yields an $O(n \log n)$ solution for $m=2$ and suggests a context that may yield good answers for arbitrary fixed $m$.

Denote the $i$-th coordinate of $u_k$ and $v_k$ by $u_k^{(i)}$ and $v_k^{(i)}$ respectively. Consider the $n$ vectors of length $m$: $$ x_i = (u_1^{(i)}, u_2^{(i)}, u_3^{(i)}, \ldots u_n^{(i)}) \in {\bf R}^m =: V $$ ($i=1,2,\ldots,n$), and the $n$ dual vectors $$ y_j = (v_1^{(j)}, v_2^{(j)}, v_3^{(j)}, \ldots v_n^{(j)}) \in V^*. $$ ($j=1,2,\ldots,n$). Then the $(i,j)$ entry of $A$ is $y_j(x_i)$, so the problem asks for the minimum or maximum of $y_j(x_i)$ as $i,j$ range independently over $\lbrace 1, 2, \dots, n \rbrace$.

Note that given $A$ there are many choices of $u_k$ and $v_k$, but the choice is tantamount to a choice of basis on $V$ and of dual basis on $V^*$, so geometrically our $y_j(x_i)$ problem depends only on $A$.

Now it's clear that the minimizing/maximizing choice of $x_i$ and $y_j$ must be vertices of the convex hull of $\lbrace x_i \rbrace$ and $\lbrace y_j \rbrace$ respectively. This recovers the known solution for $m=1$, when any bounded convex subset of $V$ has (at most) two vertices, which can be found in $O(n)$ comparisons.

For $m=2$, it is still known how to find the vertices of the convex hull (in cyclic order) in $O(n \log n)$ steps [see for instance the "Convex hull algorithms" Wikipage for references]. Once we know the vertices of the convex hull of the $x_i$, we can for each $j$ find the minimal and maximal $y_j(x_i)$ in $O(\log n)$ steps by bisection, making the overall computational cost still $O(n \log n)$.

Finding the convex hull and its structure for $m=3$, and larger fixed $m$, is harder, but at least there's some literature on this problem, and experts who can suggest good ways to proceed.

This all assumes that we don't run into difficulties like $m=1$, $u_1 = (-1,2.54)$, $u_2 = (1,-.3937)$ where there are two or more very close candidates for the minimum. To deal with that, we might assume that we can do exact arithmetic (perhaps the coordinates are quantized with fixed denominator), or tolerate an error that can be brought below $\epsilon$ in $O(\log(1/\epsilon))$ steps.

Here's a geometrical reformulation of the problem that yields an $O(n \log n)$ solution for $m=2$ and suggests a context that may yield good answers for arbitrary fixed $m$. [EDIT but see below for $m=3$ and $m \geq 4$.]

Denote the $i$-th coordinate of $u_k^{\phantom.}$ and $v_k^{\phantom.}$ by $u_k^{(i)}$ and $v_k^{(i)}$ respectively. Consider the $n$ vectors in $V := {\bf R}^m$ given by $$ x_i = (u_1^{(i)}, u_2^{(i)}, u_3^{(i)}, \ldots, u_n^{(i)}) $$ ($i=1,2,\ldots,n$), and the $n$ dual vectors $$ y_j = (v_1^{(j)}, v_2^{(j)}, v_3^{(j)}, \ldots, v_n^{(j)}) \in V^*. $$ ($j=1,2,\ldots,n$). Then the $(i,j)$ entry of $A$ is $y_j(x_i)$. Thus the problem asks for the minimum or maximum of $y_j(x_i)$ as $i,j$ range independently over $\lbrace 1, 2, \dots, n \rbrace$.

Note that given $A$ there are many choices of $u_k$ and $v_k$, but the choice is tantamount to a choice of basis on $V$ and of dual basis on $V^*$, so geometrically our $y_j(x_i)$ problem depends only on $A$.

Now it's clear that the minimizing and maximizing $x_i, y_j$ must be vertices of the convex hull of $\lbrace x_i \rbrace$ and $\lbrace y_j \rbrace$ respectively. This recovers the known solution for $m=1$, when any bounded convex subset of $V$ has (at most) two vertices, which can be found in $O(n)$ comparisons.

For $m=2$, it is still known how to find the vertices of the convex hull (in cyclic order) in $O(n \log n)$ steps [see for instance the "Convex hull algorithms" Wikipage for references]. Once we know the vertices of the convex hull of the $x_i$, we can for each $j$ find the minimal and maximal $y_j(x_i)$ in $O(\log n)$ steps by bisection, making the overall computational cost still $O(n \log n)$.

Finding the convex hull and its structure for $m=3$, and larger fixed $m$, is harder, but at least there's some literature on this problem, and experts who can suggest good ways to proceed.

EDIT Alas the current state of the art for computing convex hulls apparently limits this approach to $m=2$ and maybe $m=3$.

The Mathworld entry for "Convex Hull" reports on an $O(n \log n)$ algorithm also in dimension 3, referring to

Skiena, S. S. "Convex Hull." $\S$8.6.2 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 351–354, 1997.

But this still leaves open the question of computing in time $\tilde O(n)$ a data structure that will find the extreme point in each direction in only $n^{o(1)}$ operations, or even in significantly less than the number of vertices of the convex hull. Still, if at least one of $\lbrace x_i \rbrace$ and $\lbrace y_j \rbrace$ has a convex hull with significantly fewer than $n$ vertices then this will improve on the exhaustive search over $n^2$ entries of the matrix.

Once $m \geq 4$ it seems that it is not even known how to compute the set of vertices of the convex hull in as few as $n^2$ operations; unless the number of operations can be brought significantly below $n^2$, this means that the technique described here is limited to $m=2$ and maybe $m=3$. TIDE

All of this analysis assumes that we don't run into difficulties like $m=1$, $u_1 = (-1,2.54)$, $v_1 = (1,-.3937)$, where there are two or more very close candidates for the minimum. To deal with that, we might assume that we can do exact arithmetic (perhaps the coordinates are quantized with fixed denominator), or tolerate an error that can be brought below $\epsilon$ in $O(\log(1/\epsilon))$ steps.

Here's a geometrical reformulation of the problem that yields an $O(n \log n)$ solution for $m=2$ and suggests a context that may yield good answers for arbitrary fixed $m$.

Denote the $i$-th coordinate of $u_k$ and $v_k$ by $u_k^{(i)}$ and $v_k^{(i)}$ respectively. Consider the $n$ vectors of length $m$: $$ x_i = (u_1^{(i)}, u_2^{(i)}, u_3^{(i)}, \ldots u_n^{(i)}) \in {\bf R}^m =: V $$ ($i=1,2,\ldots,n$), and the $n$ dual vectors $$ y_j = (v_1^{(j)}, v_2^{(j)}, v_3^{(j)}, \ldots v_n^{(j)}) \in V^*. $$ ($j=1,2,\ldots,n$). Then the problem asks for the maximum of $y_j(x_i)$ as $i,j$ range independently over $\lbrace 1, 2, \dots, n \rbrace$.

Note that given $A$ there are many choices of $u_k$ and $v_k$, but the choice is tantamount to a choice of basis on $V$ and of dual basis on $V^*$, so geometrically our $y_j(x_i)$ problem depends only on $A$.

Now it's clear that the maximizing $x_i$ and $y_j$ must be vertices of the convex hull of $\lbrace x_i \rbrace$ and $\lbrace y_j \rbrace$ respectively. This recovers the known solution for $m=1$, when any bounded convex subset of $V$ has (at most) two vertices, which can be found in $O(n)$ comparisons.

For $m=2$, it is still known how to find the vertices of the convex hull (in order) in $O(n \log n)$ steps [see for instance the "Convex hull algorithms" Wikipage for references]. Once we know the vertices of the convex hull of the $x_i$, we can for each $j$ find the maximal $y_j(x_i)$ in $O(\log n)$ steps, making the overall computational cost still $O(n \log n)$.

Finding the convex hull and its structure for $m=3$, and for larger fixed $m$, is harder, but at least there's some literature on this problem, and experts who can suggest good ways to proceed.

This all assumes that we don't run into difficulties like $m=1$, $u_1 = (-1,2.54)$, $u_2 = (-1,.3937)$ where there are two or more very close candidates for the maximum. To deal with that, we might assume that we can do exact arithmetic (perhaps the coordinates are quantized with fixed denominator), or tolerate an error that can be brought below $\epsilon$ in $O(\log(1/\epsilon))$ steps.

Here's a geometrical reformulation of the problem that yields an $O(n \log n)$ solution for $m=2$ and suggests a context that may yield good answers for arbitrary fixed $m$.

Denote the $i$-th coordinate of $u_k$ and $v_k$ by $u_k^{(i)}$ and $v_k^{(i)}$ respectively. Consider the $n$ vectors of length $m$: $$ x_i = (u_1^{(i)}, u_2^{(i)}, u_3^{(i)}, \ldots u_n^{(i)}) \in {\bf R}^m =: V $$ ($i=1,2,\ldots,n$), and the $n$ dual vectors $$ y_j = (v_1^{(j)}, v_2^{(j)}, v_3^{(j)}, \ldots v_n^{(j)}) \in V^*. $$ ($j=1,2,\ldots,n$). Then the $(i,j)$ entry of $A$ is $y_j(x_i)$, so the problem asks for the minimum or maximum of $y_j(x_i)$ as $i,j$ range independently over $\lbrace 1, 2, \dots, n \rbrace$.

Note that given $A$ there are many choices of $u_k$ and $v_k$, but the choice is tantamount to a choice of basis on $V$ and of dual basis on $V^*$, so geometrically our $y_j(x_i)$ problem depends only on $A$.

Now it's clear that the minimizing/maximizing choice of $x_i$ and $y_j$ must be vertices of the convex hull of $\lbrace x_i \rbrace$ and $\lbrace y_j \rbrace$ respectively. This recovers the known solution for $m=1$, when any bounded convex subset of $V$ has (at most) two vertices, which can be found in $O(n)$ comparisons.

For $m=2$, it is still known how to find the vertices of the convex hull (in cyclic order) in $O(n \log n)$ steps [see for instance the "Convex hull algorithms" Wikipage for references]. Once we know the vertices of the convex hull of the $x_i$, we can for each $j$ find the minimal and maximal $y_j(x_i)$ in $O(\log n)$ steps by bisection, making the overall computational cost still $O(n \log n)$.

Finding the convex hull and its structure for $m=3$, and larger fixed $m$, is harder, but at least there's some literature on this problem, and experts who can suggest good ways to proceed.

This all assumes that we don't run into difficulties like $m=1$, $u_1 = (-1,2.54)$, $u_2 = (1,-.3937)$ where there are two or more very close candidates for the minimum. To deal with that, we might assume that we can do exact arithmetic (perhaps the coordinates are quantized with fixed denominator), or tolerate an error that can be brought below $\epsilon$ in $O(\log(1/\epsilon))$ steps.