Maximise the value of the minimum weight intra edge
Let $G=\left(V, E=\binom{V}{2}\right)$ be your input graph, let $n=|V|$, and call $w(u,v)$ the weight of edge $(u,v) \in E$. Let $x^* = \max_{A, B} \min_{ (u,v) \in A^2 \cup B^2} w(u,v)$ be the value of an optimal solution to your problem (here $A \cup B = V$ and $A \cap B = \emptyset$).
Suppose that you have a guess $x$ on the value of $x^*$ and let $D_x$ be the set of all edges of weight smaller than $x$. Consider the graph $G'=(V, D)$.
If $G'$ is bipartite, then the two sides of a bipartition will give you a partition of $V$ such that every intra-edge has weight at least $x$. This shows that $x \le x^*$.
If $G_x$ is not bipartite then, for every partition $A,B$ of $V$, you have $D_x \setminus (A \times B) \neq \emptyset$. Since the same must hold for every $x' \ge x$ (since $D_{x'} \supseteq D_x$) this shows that no partition of $G$ can have a measure of at least $x$. I.e., $x &gt; x^*$.
You can then sort the set  $W=\{w(u,v) \mid (u,v) \in E\}$ of all edge weights and
binary search for the value of $x^* \in W$.
The binary search will require at most $O(\log n)$ iterations, and each iteration requires time $O(n^2)$ to check whether $G_x$ is bipartite.
The overall running time is then $O(n^2 \log n)$.

If the edges are already sorted by their weight, or if the edge weights are polynomially bounded (w.r.t. $n$) you can improve the above time complexity by a factor of almost $\Theta(\log n)$.
Indeed, if you have already conducted a bipartiteness test on $G_x$, and $G_x$ was bipartite, and then you are asked to determine whether $G_{x'}$, with $x' &gt; x$, is bipartite there is no need to check all edges in $D_{x'}$. Indeed, you can get away with only checking the edges in $\Delta(x, x') = D_{x'} \setminus D_{x}$.
The idea is as follows: maintain a disjoint-set (union find) data structure $U$ on the vertices of $V$, such that if $u,v \in V$ belong to the same set in $U$, then they must also belong to the same side of the bipartition of the last tested graph $G_x$.
To be more precise: $U$ will contain one set $S$ for each isolated vertex of $G_x$ and two sets $S_1, S_2$ for each connected component $C$ of $G$ with at least $2$ vertices, where $S_1, S_2$ are the unique bipartition of $G$.
It is also convenient to store,  for each set $S_i$ in $U$, the name $\eta(S_i)$ of the set corresponding to the other side of the bipartition. Namely, $\eta(S_1) = S_2$ and $\eta(S_2)=S_1$.
If $S$ is a singleton set, then $\eta(S)$ is undefined.
Initially $x=0$ (assuming w.l.o.g. that all edge weights are non-negative) so $D_0 = \emptyset$ and $U$ contains $n$ singletons.
A bipartitness check on $G_{x'}$ can be done as follows: For each edge $(u,v) \in \Delta(x, x')$ query $U$ to find the sets $S_1,S_2$ such that $u \in S_1$ and $v \in S_2$. We distinguish some cases:

Case 1: $S_1 = S_2$. In this case $G_{x'}$ cannot be bipartite since we already know that $u$ and $v$ must be on the same side of the bipartition.

Case 2: $S_1 \neq S_2$, $\eta(S_1)$ is defined, and $\eta(S_1)=S_2$. In this case $(u,v)$ connects two vertices in different sides of the bipartition of an already existing connected component. Do nothing.

Case 3: $S_1 \neq S_2$ and $\eta(S_1)$ is either undefined or $\eta(S_1) \neq S_2$. In this case we just discovered an edge across different connected components. Perform a union operation between $\eta(S_1)$ and $S_2$ and let $S'$ be the resulting set (if $\eta(S_1)$ is undefined then $S' = S_2$).
Perform a union operation between $\eta(S_2)$ and $S_1$ and let $S''$ be the resulting set (if $\eta(S_2)$ is undefined then $S'' = S_1$).
Set $\eta(S') = S''$ and $\eta(S'')=S'$. See the figure for an example.



If all edges in $\Delta(x, x')$ are processed without ever encountering case 1, then $G_{x'}$ is bipartite.
The final algorithm checks whether $G_x$ is bipartite for $x \in W$ in order, until $G_x$ becomes not bipartite. Then it returns the predecessor $y$ of $x$ in $W$. The actual partition of $V$ can be found using standard techniques (the laziest one is to find a bipartition of $G_y$ from scratch).
All the sets $\Delta(x, x')$ can be found in time $O(n^2)$ once $E$ is sorted w.r.t. $w(\cdot)$ (if $E$ is not already sorted we can use radix sort and the fact that the weights are polynomially bounded).
Moreover, the number of find operations is $O(n^2)$ and the number of union operations is $O(n)$. Thus the overall required time $O(n^2 \alpha(n))$ where $\alpha(n)$ is the inverse Ackermann function.
Notice that $\Omega(n^2)$ is a trivial lower bound for your problem.