I am more interested in the case where the two ordered bases have identical signs of oriented volume, but we may study the problem with or without this additional requirement using a unified approach.
For convenience, let the two orthonormal bases be, instead, the columns of the orthogonal matrices $U=[u_1,\ldots, u_n]$ and $V=[v_1,\ldots,v_n]$ respectively ($n\ge2$). WLOG we may assume that $V=I_n$. Let $d_i=u_i-v_i$ and $e=(1,1,\ldots,1)$. We want to find the least possible $C\ge0$ such that $ \begin{eqnarray} 0\le\delta_C(U)&:=& \frac12\left(C\sum_i \|d_i\|^2 - \sum_{i\not=j} \langle d_i,d_j\rangle\right)\\ &=& nC - C\sum_i\langle u_i,v_i\rangle + \sum_{i\not=j}\langle u_i,v_j\rangle\\ &=& nC - (C+1)\sum_i\langle u_i,v_i\rangle + \sum_{i,j}\langle u_i,v_j\rangle\\ &=& nC - (C+1){\rm tr}(U) + {\rm tr}(ee^T U)\\ &=& nC + {\rm tr}\left([ee^T - (C+1)I_n]U\right) \end{eqnarray} $ for all $U$ with $\langle u_i,v_i\rangle\ge0$. Note that $ee^T - (C+1)I_n = Q\Lambda Q^T$ where $ \Lambda = \begin{pmatrix}n-1-C\\&-(C+1)I_{n-1}\end{pmatrix} $ and $ Q = \frac{1}{r}\begin{pmatrix} 1&-1&-1&\ldots&-1\\ 1&r-t&-t&\ldots&-t\\ 1&-t&\ddots&\ddots&\vdots\\ \vdots&\vdots&\ddots&\ddots&-t\\ 1&-t&\ldots&-t&r-t \end{pmatrix} $ with $r=\sqrt{n}$ and $t=\frac{1}{r+1}$. So $ \delta_C(U) = nC + {\rm tr}\left(\begin{pmatrix}n-1-C\\&-(C+1)I_{n-1}\end{pmatrix}Q^TUQ\right). $
If $C\ge n-1$, we always have $\delta_C(U)\ge\delta_C(I_n)=0$. However, when $C, the minimum of $\delta_C$ occurs at $U=U_{\rm opt}=Q(-1\oplus I_{n-1})Q^T = I-\frac2n ee^T$, with $\delta_C(U) = 2[C-(n-1)]<0$. Note that the columns of $U_{\rm opt}$ are exactly the basis found by Willie Wong and we have $\langle u_i,v_i\rangle\ge0$.
What if we impose a further requirement that $\mathbf{\det U = \det V}$? Since in the OP's problem context, $U$ is an estimate of $V$, in practice it may be reasonable to require that $\mathbf{\det U = \det V}$. Under our previous assumption (WLOG) that $V=I_n$, this additional requirement means $\det U=1$. In this case, we see that when $n-1-C\le(C+1)$, or equivalently, if $C\ge\frac n2-1$, we always have $\delta_C(U)\ge\delta_C(V)=0$. When $n-1-C>(C+1)$, if we let $R(\theta)$ denotes the rotation matrix by an angle $\theta$, then $\delta_C(U)=-[n-1-C-(C+1)]<0$ when $U = Q(R(\frac\pi2)\oplus I_{n-2})Q^T$. Therefore, we conclude that $\frac n2-1$ is the least possible $C$ that makes $\delta_C(U)\ge0$ for all $U$ such that $\det(U)=\det(V)$ and $\langle u_i,v_i\rangle\ge0$ for all $i$. Unfortunately, we do not know which nontrivial $U$ (i.e. some $U\not=V$) will make the inequality sharp. Without the constraint $\langle u_i,v_i\rangle\ge0$, $U = Q(R(\pi)\oplus I_{n-2})Q^T$ is a minimizer of $\delta_{\frac n2-1}$. It can be shown that this $U$ will make some $\langle u_i,v_i\rangle$ negative, however.