• We present homogeneous, sub-horizontal branch photometry of twenty dwarf spheroidal satellite galaxies of M31 observed with the Hubble Space Telescope. Combining our new data for sixteen systems with archival data in the same filters for another four, we show that Andromeda dwarf spheroidal galaxies favor strikingly red horizontal branches or red clumps down to ~10^{4.2} Lsun (M_V ~ -5.8). The age-sensitivity of horizontal branch stars implies that a large fraction of the M31 dwarf galaxies have extended star formation histories (SFHs), and appear inconsistent with early star formation episodes that were rapidly shutdown. Systems fainter than ~10^{5.5} Lsun show the widest range in the ratios and morphologies of red and blue horizontal branches, indicative of both complex SFHs and a diversity in quenching timescales and/or mechanisms, which is qualitatively different from what is currently known for faint Milky Way (MW) satellites of comparable luminosities. Our findings bolster similar conclusions from recent deeper data for a handful of M31 dwarf galaxies. We discuss several sources for diversity of our data such as varying halo masses, patchy reionization, mergers/accretion, and the environmental influence of M31 and the Milky Way on the early evolution of their satellite populations. A detailed comparison between the histories of M31 and MW satellites would shed signifiant insight into the processes that drive the evolution of low-mass galaxies. Such a study will require imaging that reaches the oldest main sequence turnoffs for a significant number of M31 companions.