$\newcommand\Vol{\mathop{\mathrm{Vol}}}\newcommand\tr{\mathop{\mathrm{tr}}}$The estimate on the sum of determinants is rewritten.
Here is the proof that one of the eigenvalues indeed does not exceed $1/3$;
Let $X$ be the matrix with columns $\mathbf x_1$ and $\mathbf x_2$ (writing $X=(\mathbf x_1,\mathbf x_2)$); then $M=XX^\top$. Therefore, $M_{ij}=X_{ij}X_{ij}^\top$, where $X_{ij}$ is the submatrix of $X$ with only $i$th and $j$th rows left.
We are to estimate $t_{ij}=\tr M_{ij}$ and $d_{ij}=\det M_{ij}$. The first one is simple, as
$$
\sum t_{ij}=2\|\mathbf x_1\|^2+2\|\mathbf x_2\|^2=4.
$$
For the second, introduce the Gram matrix $\Gamma=X^\top X$ of the $\mathbf x_1,\mathbf x_2$ and use the Cauchy-Binet formula to write
$$
1\geq \Vol(\mathbf x_1,\mathbf x_2)^2=\det\Gamma=\det X^\top X=\sum_{(i,j)}\det X_{ij}^2=\sum_{(i,j)} d_{ij}.
$$
(Notice that the formula for the sum of traces can be also viewed as an instance of the same formula.)
Assume now that the smallest eigenvalue $\lambda_{ij}$ of $M_{ij}$ is larger than $1/3$, for all $i,j$; then both eigenvalues of $M_{ij}$ lie on $(1/3,3d_{ij})$. Since the dunction $x+d_{ij}/x$ attains its maximum at both endpoints of the segment $[1/3,3d_{ij}]$, we have
$$
t_{ij}<\frac13+3d_{ij},
$$
and hence
$$
4=\sum t_{ij}<1+3\sum d_{ij}\leq 4,
$$
which is a contradiction.
Generalizations. 1. (Here was a wrong proof of the following conjecture, sorry; I still believe in it and will try to prove.)
Conjecture. Let $d\geq 2$ be an integer. Assume that $\mathbf x_1,\dots,\mathbf x_{d-1}$ are unit vectors in $\mathbb R^d$, and let $M=\sum \mathbf x_i\mathbb x_i^\top$. Let $M_i$ denote the submatrix of $M$ obtained by removing the $i$th row and the $i$th column. Then one of the $M_i$ has an eigenvalue not exceeding $1/d$.
This bound is achieved if $\mathbf x_1,\dots,\mathbf x_{d-1}$is any orthonormal base in the hyperplane orthogonal to the all-ones vector $\mathbf 1=(1,1,\dots,1)^\top$.. Indeed, in this case $M=I-\frac1d\mathbf 1\mathbf 1^\top$, and the least eigenvalue of each $M_i$ is $1/d$.
2. This is to partially answer a (now deleted) question by the OP on what happens in $\mathbb R^4$.
A similar method works id $\mathbf x_1,\mathbf x_2$ are unit vectors in $R^4$. In this case, we have six matrces of the form $M_{ij}$, with
$$
\sum_{(i,j)}d_{ij}\leq 1 \quad\text{and}\quad \sum_{(i,j)}t_{ij}=6.
$$
Now, if $\lambda_0$ is the minimmal eigenvalue, then we again have $t_{ij}\leq \lambda_0+d_{ij}/\lambda_0$, hence
$$
6=\sum_{(i,j)}t_{ij}\leq 6\lambda_0+\frac1{\lambda_0}\sum_{(i,j)}d_{i,j}\leq 6\lambda_0+\frac1{\lambda_0},
$$
whence $\lambda_0\leq \frac12-\frac1{2\sqrt3}$ (since it could not happen that all eigenvalues are at least $\frac12+\frac1{2\sqrt3}$).
I am, however, unaware of whether this estimate is sharp.
