Some hints : all methods that attempt to describe the ground state of a many-body electronic system are often reduced to one electron in a mean-field or effective potential that includes the effects of the other electrons and the potential of the nuclei with some corrections. The eigenfunction is expanded in a chosen basis set. The most accurate description must include an infinite basis set with a non-local potential, which is definitely impractical for a "classical computer". A mean-field potential is a good approximation if the effective potential, which depends strongly on the electronic distribution, is not widely affected by a large variation of this electronic distribution. This is precisely the case at large interatomic distances, where all approximations, especially density methods, give inaccurate results and have poor convergence.
in which methods like Hartree-Fock, MP2, CISD, and CCSD get progressively less accurate as the bond length increases
Hartree-Fock (HF), related methods or generally wave function based methods are more interesting in this case, they include non local potential (exchange), it gives self-interaction free eigenvalues, the basis set could not converge quickly just because of the configuration between localized orbitals and a very small tendency to be delocalized, the error is due to the mean field approximation.
This seems to be related to what chemists call "strong correlation".
A "strongly correlated" behavior is exactly the case where the overlap between the atoms is small and the repulsion on the incoming charge becomes non-negligible compared to the translational symmetry creating the bond.
This seems counter-intuitive to me, since, using N2 as an example, as the bond is stretched, I would assume that the electrons associated to different nuclei interact less (i.e: the Hamiltonian approximately factorizes into a tensor product of two easier-to-simulate Hamiltonians for each nuclei).
As a consequence of the previous arguments, the hamiltonian is only separable if the electrons are not correlated, at large interatomic distances the coulomb repulsion is large $U \gg $, a single particule approximation will never lead to the exact ground state and the hamiltonian is not strictly speaking separable. The wave function of the system is $\psi(r_1,r_2,r_3,...,r_n)$, for simplicity, let's take the case $\psi(r_1,r_2)$, if the atoms are far apart an not interaction $\psi(r_1,r_2) = \phi_1(r_1)\phi_2(r_2)$, when the wave function overlaps, the wave function $\phi_1$ is transferred to another atom with by a translating operator $\hat{T}$ and reciprocally for $\phi_2$, the translation operation is the generator of the bond, the commutator [$\hat{H}$,$\hat{T}]=0$ if the potential is translational symmetric. Only a local potential $V(r_1,r_2)=V_0(r)$ is translational symmetric, $V(r_1,r_2)$ is not translational symmetric in this configuration, the translational symmetry is enhanced at small distances, while at large distance the operator is reduced and $V(r_1,r_2)$ is significant, the system is strongly correlated [$\hat{H}$,$\hat{T}$]$\neq 0$ , $\psi(r_1,r_2) \neq \phi_1(r_1)\phi_2(r_2)$, any one-electron approximation will never give the exact ground state.
I would assume that N2 would be harder to simulate when the nuclei are closer.
The nuclei are often treated classically, at very small distances, things would have been very complicated, the problem arises often from the basis set. Approximations like DFT works fine at small distances, because the overlap is large and the density do not vary much, a mean field potential holds and the result can be very accurate.