We present the discovery of two new dwarf galaxies, Andromeda XXI and Andromeda XXII, located in the surroundings of the Andromeda and Triangulum galaxies (M31 and M33). These discoveries stem from the first year data of the Pan-Andromeda Archaeological Survey (PAndAS), a photometric survey of the M31/M33 group conducted with the Megaprime/MegaCam wide-field camera mounted on the Canada-France-Hawaii Telescope. Both satellites appear as spatial overdensities of stars which, when plotted in a color-magnitude diagram, follow metal-poor, [Fe/H]=-1.8, red giant branches at the distance of M31/M33. Andromeda XXI is a moderately bright dwarf galaxy (M_V=-9.9+/-0.6), albeit with low surface brightness, emphasizing again that many relatively luminous M31 satellites still remain to be discovered. It is also a large satellite, with a half-light radius close to 1 kpc, making it the fourth largest Local Group dwarf spheroidal galaxy after the recently discovered Andromeda XIX, Andromeda II and Sagittarius around the Milky Way, and supports the trend that M31 satellites are larger than their Milky Way counterparts. Andromeda XXII is much fainter (M_V=-6.5+/-0.8) and lies a lot closer in projection to M33 than it does to M31 (42 vs. 224 kpc), suggesting that it could be the first Triangulum satellite to be discovered. Although this is a very exciting possibility in the context of a past interaction of M33 with M31 and the fate of its satellite system, a confirmation will have to await a good distance estimate to confirm its physical proximity to M33. Along with the dwarf galaxies found in previous surveys of the M31 surroundings, these two new satellites bring the number of dwarf spheroidal galaxies in this region to 20.