An inequality on some pairs of orthogonal vectors Let $n,k\geq 1$. Suppose that
$a_1, \ldots, a_n\in \mathbb{R}^k$, $b_1, \ldots, b_n\in \mathbb{R}^k$
and $a_i^T b_i = 0$ for $i=1,\dots, n$. Is it true that
$$
\sum_{i=1}^n \|a_i\|_2^2 + \sum_{i=1}^n \|b_i\|_2^2 \geq \frac3n \sum_{i,j=1}^n | a_i^T b_j | 
$$

A matrix reformulation of the problem:
Let $A$ be a matrix, we have (e.g. see here) $\|A\|_{(1)} = \frac 12 \min_{A=U^TV} (\|U\|_F^2 + \|V\|_F^2)$
where $\|A\|_{(1)}$ is the sum of singular values of $A$ (known as the trace/nuclear norm). Now, the above problem could be stated as follows

Let $A = [a_{ij}]$ be an $n \times n$ matrix with zero diagonal. Is
it true $$ \|A\|_{(1)} \geq \frac12\frac{3}{n} \sum_{i,j}|a_{ij}| $$

 A: I guess it is time to post the proof for the constant $\pi$ in the $k=2$ case to avoid any further controversy there. It won't hurt because it is rather clear what its boundaries are, so nobody will get stuck with a dead end idea (which might happen if I post the $1+\sqrt 3$ argument in higher dimension).
As Ivan observed, we need to estimate the integral $\langle (f\mu)*K,g\mu\rangle=\int_{\mathbb T}[(f \mu)*K]\,d(g \mu)$ where $\mu$ is the (let's say, normalized to $\mu(\mathbb T)=1$) counting measure of the set of directions of $a_i$, $f$ describes the lengths of $a_i$, $g$ describes the lengths of $b_i$, $\mathbb T=\mathbb R/\mathbb Z$ and $K(t)=|\sin 2\pi t|$. Since $K$ is real even, we can write $f=u+v$, $g=u-v$ and get $\langle (f\mu)*K,g\mu\rangle=\langle (u\mu)*K,u\mu\rangle-\langle (v\mu)*K,v\mu\rangle$. Now, going to the Fourier side and observing that $\widehat K(n)=\frac 1\pi\frac{1+\cos(\pi n)}{1-n^2}$ (i.e., $\widehat K(0)=\frac 2\pi$ and $\widehat K(n)\le 0$ for $n\ne 0$, $\sum_{n\ne 0}\widehat K(n)=-\frac 2\pi$), we get
$$
\langle (u\mu)*K,u\mu\rangle=\sum_n \widehat K(n)|\widehat{(u\mu)}(n)|^2\le \frac 2\pi|\widehat{(u\mu)}(0)|^2\le \frac 2\pi\int_{\mathbb T} u^2\,d\mu
$$
and
$$
-\langle (v\mu)*K,v\mu\rangle=-\sum_n \widehat K(n)|\widehat{(v\mu)}(n)|^2\le \frac 2\pi\max_{n\ne 0}|\widehat{(v\mu)}(n)|^2\le \frac 2\pi\int_{\mathbb T} v^2\,d\mu\,,
$$
so
$$
\langle (f\mu)*K,g\mu\rangle\le \frac 2\pi\left[\int_{\mathbb T} u^2\,d\mu+
\int_{\mathbb T} v^2\,d\mu\right]=\frac 1\pi\left[\int_{\mathbb T} f^2\,d\mu+\int_{\mathbb T} g^2\,d\mu\right]\,,
$$
which is equivalent to the original inequality with constant $\pi$ instead of $3$. The example showing that $\pi$ is sharp has already been mentioned.
Unfortunately, this simple argument seems rather hard to generalize to higher dimensions (though I may miss some trick). However, it may be possible to reduce the general case to the 2-dimensional one somehow (though I don't know how), in which case the above proof may become useful.
A: $\def\Tr{\mathrm{Tr}}\def\Mat{\mathrm{Mat}}$I've been thinking about this problem a bunch, and I think the correct bound  is
$$ \sum_{i,j} |A_{ij}| \leq \left( \cot \frac{\pi}{2n}  \right)|A|_{(1)}. $$
As $n \to \infty$, we have $\cot \tfrac{\pi}{2n} \sim \tfrac{2n}{\pi}$, so this matches the $\pi$ bound that fedja proved for $k=2$.
In particular, I will prove that this bound is correct for skew-symmetric $A$; almost all the work is not due to me but to a paper of Grzesik, Kral, Lovasz and Volec which was pointed out in a deleted answer by another user.
I'll write $\sigma_1(A) \geq \sigma_2(A) \geq \cdots$ for the singular values of $A$. Note that we have
$$\sum |A_{ij}| = \max_{P \in \mathrm{Mat}_n(\pm 1)} \Tr(AP) $$
and
$$|A|_{(1)} = \max_{Q \in O(n)} \Tr(AQ). $$
Here $P$ is ranging over $\pm 1$ matrices, and $Q$ is ranging over the orthogonal group.
We may replace the orthogonal group by its convex hull without changing the max. The convex hull of $O(n)$ is the set of matrices of operator norm $\leq 1$; call that $B_1$.
So
$$|A|_{(1)} = \max_{R \in B_1} \Tr(AR). $$
As a warm up, let's consider the best inequality we can prove of the form $\sum |A_{ij}| \leq C |A|_{(1)}$ without imposing that the diagonal is $0$. The answer is that the best is $C = n$, and that is easy to prove by elementary means, but I want to demonstrate my approach instead. So we want to find a $C$ such that, for every $\pm 1$ matrix $P$ and for every matrix $A$, we have $\Tr(AP) \leq C \max_{R \in B_1} \Tr(AR)$. Since $B_1$ is convex, this is the same as asking for $C$ such that $P \in C B_1$. In other words, we want to bound $\sigma_1(P)$ for $P$ in $\Mat_n(\pm 1)$. It wouldn't be hard to obtain the bound $n$ from here, but we move on.
Let's leave the warm up and get to the real problem. What we actually want is that $\Tr(AP) \leq C \max_{R \in B_1} \Tr(AR)$ for $A$ having zero diagonal. Thus, we only need $\pi(P)$ to lie in $\pi(C B_1)$, where $\pi$ is orthogonal projection onto matrices of diagonal $0$. In other words, we want $P$ to lie in $CB_1 + \Delta$ where $\Delta$ is the vector space of diagonal matrices. So we come to the following problem:
Problem 1: Find the best constant $C_1$ such that, for every $\pm 1$ matrix $P$, there is a diagonal matrix $D$ with $\sigma_1(P+D) \leq C_1$.
Unfortunately, it seems hard to even guess a rule for choosing the optimal $D$. For example, if $P$ is identically $1$, the best choice of $D$ is $-\frac{n}{2} \mathrm{Id}_n$.
Having no success here, I move on to the case of $A$ skew symmetric. We now can consider only skew symmetric $P$ (which are $0$ on the diagonal and $\pm 1$ off the diagonal.) For such a $P$, we now want to solve the problem:
Problem 2: Find the best constant $C_1$ such that, for every skew-symmetric $\pm 1$ matrix $P$, there is a symmetric matrix $H$ with $\sigma_1(P+H) \leq C_1$.
Fortunately, here I can make a little progress. It turns out that the symmetric matrix is irrelevant!
Lemma: Let $P$ be a skew symmetric matrix and $H$ a symmetric matrix. Then $\sigma_1(P+H) \geq \sigma_1(P)$.
Proof: Since $P$ is skew symmetric, it is diagonalizable over $\mathbb{C}$ with purely imaginary eigenvalues, and the largest such is $i \sigma_1(P)$. Let $v$ be an eigenvector with $P v = i \sigma_1 v$. Writing $\dagger$ for the conjugate transpose, normalize $v^{\dagger} v =1$. Then $\sigma_1(P+H) \geq | v^{\dagger} (P+H) v | = |i \sigma_1 + v^{\dagger} H v|$. But $v^{\dagger} H v$ is real, so $|i \sigma_1 + v^{\dagger} H v| \geq \sigma_1$. $\square$.
Thus, we have reduced to the problem:
Problem 3: Find the largest operator norm of any skew-symmetric $\pm 1$ matrix.
Another poster answered and then deleted his answer to point out that this problem is solved in Lemma 11 of Cycles of a given length in tournaments! (On reflection, I have removed this poster's name since they choose to self-delete, but I hope they will identify themselves and claim the credit; this is useful!) The largest operator norm is always achieved by the matrix which is $1$'s above the diagonal and $-1$'s below it. (As well as by the many other matrices which are conjugate to this one by signed permutation matrices.)
This matrix can be explicitly diagonalized:
The eigenvectors are of the form $(1, \zeta, \zeta^2, \ldots, \zeta^{n-1})$ where $\zeta = \exp(\pi i (2j+1)/(2n))$. The corresponding eigenvalues are $i \cot \tfrac{(2j+1) \pi}{2n}$. In particular, the largest singular value is $\cot \tfrac{\pi}{2n}$, thus explaining my guess.
I am guessing this is optimal for Problem 1 as well as Problem 2, but this is based on a very weak intuition that skew symmetric choices are good, plus fedja's answer.
A: We shall prove the inequality
\begin{equation*}
    \sum_{i=1}^n|a_i|^2+\sum_{i=1}^n|b_i|^2\ge\frac Cn \sum_{i,j=1}^n|a_ib_j| \tag{0}
\end{equation*}
with $C:=4/\sqrt3=2.309\dots$.
We use the notations $|a|:=\|a\|_2$ and $ab:=a^Tb$. Without loss of generality, the $a_i$ and $b_j$'s are nonzero vectors.
For two nonzero vectors $a$ and $b$, let $d(a,b)\in[0,\pi/2]$ denote the angle between the straight lines carrying the vectors $a$ and $b$. The function $d$ is a pseudometric, since the big circles are the geodesic lines on the 2D sphere.
For $i,j$ in $[n]:=\{1,\dots,n\}$, let then
$$d_{ij}:=d(a_i,b_j)=\arccos c_{ij},\quad c_{ij}:=\frac{|a_ib_j|}{|a_i|\,|b_j|},$$
so that $d_{ij}\in[0,\pi/2]$ is the angle between the straight lines carrying the vectors $a_i$ and $b_j$.
Take any $i,j,k$ in $[n]:=\{1,\dots,n\}$. Since $a_ib_i=0$ and $d$ is a pseudometric,
\begin{equation*}
    |d_{ki}-\pi/2|=|d_{ki}-d_{ii}|\le d(a_i,a_k)=:t
\end{equation*}
and hence
\begin{equation*}
    |a_kb_i|\le|a_k|\,|b_i|\sin t. \tag{1}
\end{equation*}
Moreover, again because $d$ is a pseudometric,
\begin{equation*}
    t\le d_{ij}+d_{kj}. \tag{2}
\end{equation*}
If $d_{ij}+d_{kj}\ge\pi/2$, then $d_{kj}\in[\pi/2-d_{ij},\pi/2]\subseteq[0,\pi/2]$ and hence
$c_{ij}^2+c_{kj}^2\le\cos^2 d_{ij}+\cos^2(\pi/2-d_{ij})=1\le5/4$, so that
\begin{equation*}
    c_{ki}^2+c_{ij}^2+c_{kj}^2\le9/4. \tag{3}
\end{equation*}
If $d_{ij}+d_{kj}<\pi/2$, then (2) implies $\sin t\le\sin(d_{ij}+d_{kj})$. So, by (1),
\begin{equation*}
    c_{ki}\le c_{kj}\sqrt{1-c_{ij}^2}+c_{ij}\sqrt{1-c_{kj}^2}.
\end{equation*}
Now the Cauchy--Schwarz inequality yields
\begin{equation*}
    c_{ki}^2\le(c_{kj}^2+c_{ij}^2)(2-c_{kj}^2-c_{ij}^2).
\end{equation*}
The latter inequality together with the conditions that $c_{ki}^2,c_{kj}^2,c_{ij}^2$ are in $[0,1]$ implies (3). Thus, (3) holds for any $i,j,k$.
Therefore,
\begin{equation*}
    \frac94\,n^3\ge\sum_{i,j,k\in[n]}(c_{ki}^2+c_{ij}^2+c_{kj}^2)
    =3n\sum_{i,j\in[n]}c_{ij}^2,
\end{equation*}
so that
\begin{equation*}
    \sum_{i,j\in[n]}c_{ij}^2\le\frac34\,n^2,
\end{equation*}
which further implies
\begin{align*}
    \sum_{i,j\in[n]}|a_ib_j|&=\sum_{i,j\in[n]}c_{ij}|a_i|\,|b_j| \\ 
    &\le\sqrt{\sum_{i,j\in[n]}c_{ij}^2}
    \sqrt{\sum_{i,j\in[n]}|a_i|^2\,|b_j|^2} \\ 
    &=\sqrt{\sum_{i,j\in[n]}c_{ij}^2}
    \sqrt{\sum_{i\in[n]}|a_i|^2}\,\sqrt{\sum_{j\in[n]}|b_j|^2} \\ 
    &\le\sqrt{\frac34\,n^2}\times\frac12\,\Big(\sum_{i\in[n]}|a_i|^2+\sum_{j\in[n]}|b_j|^2\Big),
\end{align*}
so that we do have (0) with $C=4/\sqrt3$.
