Both answers are $-n$.
Lemma $\,$ For any $G\in\mathcal{M_{n\times n}}(\mathbb{R})$
$$\text{tr} (G^TG)+ \text{tr} (G^2) \ge 0$$
And the equality holds iff $G^T=-G$.
Proof $\,\,$ Write $G=(g_{ij})_{n\times n}$. Then we have
\begin{align}
(G^TG)_{ii} &= \sum_{j=1}^n g^2_{ji}\\
(G^2)_{ii} &= \sum_{j=1}^n g_{ij} g_{ji}\\
(GG^T)_{ii} &= \sum_{j=1}^n g^2_{ij}
\end{align}
Via the definition of trace, we have
\begin{align}
\text{tr} (G^TG)+ \text{tr} (G^2)
&=
\frac{1}{2} \text{tr}(G^TG) + \text{tr}(G^2) + \frac{1}{2}\text{tr}(GG^T)
\\&=
\sum_{i=1}^n \sum_{j=1}^n \left(\frac{1}{2}g^2_{ji} + g_{ij} g_{ji} +\frac{1}{2}g^2_{ij}\right)
\\ &= \frac{1}{2} \sum_{j=1}^n \sum_{i=1}^n (g_{ij} + g_{ji} )^2
\\ &\ge 0
\end{align}
And the equality holds iff $g_{ij}=-g_{ji}$ , i.e. $G^T=-G$.
Q.E.D.
Then we come back to the original problem. Put $G=(g_{ij})_{n\times n}$.
Note that $g_{ii}=0$ and $\|g_i\|=1$, then from the definition of trace we know
$$\sum_{i=1}^n\sum_{j\neq i} g_{ij}\cdot g_{ji}= \text{tr}(G^2)$$
$$\text{tr}(G^TG)=\sum_{i=1}^n \|g_i\| =n$$
Thus via the lemma we have
$$\sum_{i=1}^n\sum_{j\neq i} g_{ij}\cdot g_{ji} = \text{tr}(G^2)\ge -n$$
For $n$ being odd, define $g_{ij}$ by
$$
g_{ij} =
\begin{cases}
(-1)^{i+j}\frac{1}{\sqrt{n-1}} & \mbox{if } i<j \\
-g_{ji} & \mbox{if } i>j\\
0 & \mbox{if } i=j
\end{cases}
$$
For example when $n=3$ we define $G$ by
$\begin{pmatrix}
0 & -\frac{1}{\sqrt 2} & +\frac{1}{\sqrt 2} \\
+\frac{1}{\sqrt 2} & 0 & -\frac{1}{\sqrt 2} \\
-\frac{1}{\sqrt 2} & +\frac{1}{\sqrt 2} & 0
\end{pmatrix}$.
For $n \equiv 0 \mod 4$, we define $G$ by
$$
g_{ij} =
\begin{cases}
(-1)^{i+j} \sqrt\frac{2}{n} & \mbox{if } i\le \frac{n}{2} \mbox{ and } j > \frac{n}{2} \\
-g_{ji} & \mbox{if } i > \frac{n}{2} \mbox{ and } j \le \frac{n}{2}\\
0 & \mbox{other cases}
\end{cases}
$$
For $n \equiv 2 \mod 4$, we define $G$ by
$$
g_{ij} =
\begin{cases}
(-1)^{i+j} \sqrt\frac{2}{{n-2}} & \mbox{if } i\le \frac{n}{2} \mbox{ , } j > \frac{n}{2} \mbox{ and } i > j-\frac{n}{2} \\
-g_{{j-\frac{n}{2}},{i+\frac{n}{2}}} & \mbox{if } i\le \frac{n}{2} \mbox{ , } j > \frac{n}{2} \mbox{ and } i< j-\frac{n}{2} \\
-g_{ji} & \mbox{if } i > \frac{n}{2} \mbox{ and } j \le \frac{n}{2}\\
0 & \mbox{other cases}
\end{cases}
$$
For example when $n=4$ we define $G$ by $\begin{pmatrix}
0 & 0 & +\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} \\
0 & 0 & -\frac{1}{\sqrt 2} & +\frac{1}{\sqrt 2} \\
-\frac{1}{\sqrt 2} & +\frac{1}{\sqrt 2} & 0 & 0 \\
+\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} & 0 & 0 \\
\end{pmatrix}$,
and when $n=6$ we define $G$ by
$\begin{pmatrix}
0 & 0 & 0 & 0 & +\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} \\
0 & 0 & 0 & -\frac{1}{\sqrt 2} & 0 & +\frac{1}{\sqrt 2} \\
0 & 0 & 0 & +\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} & 0 \\
0 & +\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} & 0 & 0 & 0 \\
-\frac{1}{\sqrt 2} & 0 & +\frac{1}{\sqrt 2} & 0 & 0 & 0 \\
+\frac{1}{\sqrt 2} & -\frac{1}{\sqrt 2} & 0 & 0 & 0 & 0 \\
\end{pmatrix}$.
Note that the construction satisfies both 1 and 2. Thus for $n\ge 3$, the minimums are always $-n$.
We have that
$$\angle(v,u_i) \leq \frac{\pi}{4} \iff \frac{v\cdot u_k}{|v||u_k|}\ge \frac {\sqrt 2} 2 \iff v\cdot u_k\ge \frac {\sqrt 2} 2|v||u_k|$$
and we need to check that
$$\frac{v\cdot w}{|v||w|}\ge \frac {\sqrt 2} 2\iff v \cdot (c_1u_i+c_2u_j) \ge \frac {\sqrt 2} 2|v||c_1u_i+c_2u_j|$$
which is true indeed
$$v \cdot (c_1u_i+c_2u_j) =c_1v\cdot u_i + c_2v\cdot u_j \ge \frac {\sqrt 2} 2|v|\left(c_1|u_i|+c_2|u_j|\right)$$
and by triangle inequality
$$c_1|u_i|+c_2|u_j|\ge |c_1u_i+c_2u_j|$$
Best Answer
It is the minimum; here is a proof. Note $\cos(\theta_{i,j}) = \langle u_i, u_j \rangle$. So, letting $u = \sum_i u_i$, $\sum_i \sum_{j \not = i} \cos(\theta_{i,j}) = \sum_i \langle u_i, \sum_{j \not = i} u_j \rangle = \sum_i \langle u_i, u-u_i \rangle = \sum_i [\langle u_i,u \rangle-1] = \langle u,u \rangle - n$. Note that equality is attained if and only if $u=0$, which is the case for equidistant unit vectors.