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
<a href="http://en.wikipedia.org/wiki/Convex_hull_algorithms">
"Convex hull algorithms" Wikipage</a> 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.