We compare the spectra of anomalous He nuclei measured in the heliosphere by the IMP, Voyager, and Pioneer spacecraft at heliospheric distances ranging from 1 to over 80 AU in the time period from 1977 to 2003. Striking differences in the energy spectra of these nuclei are found between positive and negative solar magnetic polarity cycles. These differences are such that the spectra observed in negative polarity cycles appear to be greatly deficient in particles with energies of less than ~15 MeV but have an excess intensity above >25 MeV, relative to the spectra observed in positive cycles. These spectral differences are complex and may be related to both solar modulation effects inside of the heliospheric termination shock as well as differences occurring at or near the termination shock itself. At the modulation minimum in 1998 when V2 was at a distance of 56 AU and V1 at 71 AU, a high intensity of low-energy anomalous He particles was observed with a peak in the spectrum at ~5 MeV/nuc. In late 2001 after the solar magnetic polarity had changed from positive to negative and the 11-year solar modulation had increased, the previous high intensities of the anomalous He nuclei seen in 1998 were greatly reduced at both V1 and V2, and the energy of the peak intensity had moved up to ~20--25 MeV/nuc. However, in both polarity periods the highest-energy part of this spectrum above ~30 MeV/nuc is similar with a slope of -2.8 ¿ 0.2. The details of these complex spectral changes are described in this paper.