Can anyone explain why the exchange contribution to the total energy is negative?
I find it misleading that exchange interaction is treated as something that changes total energy of the system. This lowering of energy is actually due to the Hartree-Fock scheme being in principle inexact, and is not really specific to indistinguishable particles.
Let me elaborate. Consider a hypothetical system of distinguishable particles with exactly the same masses, charges and spins (and all their other properties entering the Schrödinger's equation). Let these parameters be equal to those of an electron. Now, if you solve the Schrödinger's equation for this system in the electromagnetic field of an atomic nucleus, you'll get some (spinor-valued) wavefunctions $\Psi_n$, where $n$ enumerates the states. These wavefunctions won't in general be antisymmetric.
But the symmetry of the Hamiltonian, namely its invariance with respect to exchange of a pair of particles (since all their relevant properties are the same), tells us that there's a large degeneracy. If you linearly combine the degenerate states corresponding to the same energy so as to get symmetric $\Psi_k^{\mathrm s}$ and antisymmetric $\Psi_k^{\mathrm a}$ linear combinations, these will still be solutions of the Schrödinger's equation we started with.
If you throw away the symmetric solutions and only leave the antisymmetric ones, these will actually be the solutions for the case where our particles are indistinguishable. You see? We've just arrived at exchange interaction between indistinguishable particles, without any change in energy. What we got is just a possible increase in ground state energy due to losing a bunch of states (and thus renaming one of the formerly excited states to the ground one).
Now, why do we get lowering of states in inexact schemes when we introduce such antisymmetrization? That's directly related (at least for the antisymmetrized ground state) to the variational principle, which tells us that an approximation of a ground state will always have mean energy $E_{\text{approx}}$ (which is the Rayleigh quotient) obeying
$$E_{\text{approx}}\ge E_0,$$
where $E_0$ is the exact ground state energy.
Before introducing the Slater determinant, the trial wavefunction was smooth and generally nonzero at the loci of electron-electron collisions. But the exact (even non-symmetric) eigenfunction should have a local minimum (a cusp, see here for an example) or a (smooth) zero at such loci due to the Coulomb repulsion. After antisymmetrization, many of such loci of collisions will get zeros. This will make the approximation better, and the mean energy lower, closer to the exact eigenenergy.
If instead of Hartree-Fock method we used some other approximation that had begun with exact treatment of electron collisions, sacrificing something other, then such antisymmetrization might not lead to any improvement in estimation of eigenenergies (limit case being very precise numerical treatment yet disregarding Pauli principle, which is basically equivalent to an exact solution for distinguishable particles).