We present the first comparison between the lifetime star formation histories (SFHs) of M31 and Milky Way (MW) satellites. Using the Advanced Camera for Surveys on board the Hubble Space Telescope, we obtained deep optical imaging of Andromeda II (And II; MV = -12.0 log(M sstarf/M ⊙) ~ 6.7) and Andromeda XVI (And XVI; MV = -7.5 log(M sstarf/M ⊙) ~ 4.9) yielding color-magnitude diagrams that extend at least 1 mag below the oldest main-sequence turnoff, and are similar in quality to those available for the MW companions. And II and And XVI show strikingly similar SFHs: both formed 50%-70% of their total stellar mass between 12.5 and 5 Gyr ago (z ~ 5-0.5) and both were abruptly quenched ~5 Gyr ago (z ~ 0.5). The predominance of intermediate age populations in And XVI makes it qualitatively different from faint companions of the MW and clearly not a pre-reionization fossil. Neither And II nor And XVI appears to have a clear analog among MW companions, and the degree of similarity in the SFHs of And II and And XVI is not seen among comparably faint-luminous pairs of MW satellites. These findings provide hints that satellite galaxy evolution may vary substantially among hosts of similar stellar mass. Although comparably deep observations of more M31 satellites are needed to further explore this hypothesis, our results underline the need for caution when interpreting satellite galaxies of an individual system in a broader cosmological context. Based on observations made with the NASA/ESA Hubble Space Telescope, obtained at the Space Telescope Science Institute, which is operated by the Association of Universities for Research in Astronomy, Inc., under NASA contract NAS 5-26555. These observations are associated with program #13028.