Why must basis sets used in computations be non-orthogonal? While constructing basis sets for calculations using Hartree Fock, the basis set must be non-orthogonal. And because of this, we go through many steps to put the overlap and density matrices in the 'right' basis. (See Modern Quantum Chemistry (Szabo and Ostlund) or David Sherill's notes online). 

My question is: why must this basis be non-orthogonal?
It does not have to be non-orthogonal. The basis set can be arbitrary, and one usually uses the chemically motivated Ansatz with atomic orbitals (LCAO), which just happen to be non-orthogonal. An alternative would be to use a plane wave basis set, which are orthogonal.