We report on the discovery of three new dwarf galaxies in the Local Group. These galaxies are found in new CFHT/MegaPrime g,i imaging of the south-western quadrant of M31, extending our extant survey area to include the majority of the southern hemisphere of M31's halo out to 150 kpc. All these galaxies have stellar populations which appear typical of dwarf spheroidal (dSph) systems. The first of these galaxies, Andromeda XVIII, is the most distant Local Group dwarf discovered in recent years, at ~1.4 Mpc from the Milky Way (~ 600 kpc from M31). The second galaxy, Andromeda XIX, a satellite of M31, is the most extended dwarf galaxy known in the Local Group, with a half-light radius of r_h ~ 1.7 kpc. This is approximately an order of magnitude larger than the typical half-light radius of many Milky Way dSphs, and reinforces the difference in scale sizes seen between the Milky Way and M31 dSphs (such that the M31 dwarfs are generally more extended than their Milky Way counterparts). The third galaxy, Andromeda XX, is one of the faintest galaxies so far discovered in the vicinity of M31, with an absolute magnitude of order M_V ~ -6.3. Andromeda XVIII, XIX and XX highlight different aspects of, and raise important questions regarding, the formation and evolution of galaxies at the extreme faint-end of the luminosity function. These findings indicate that we have not yet sampled the full parameter space occupied by dwarf galaxies, although this is an essential pre-requisite for successfully and consistently linking these systems to the predicted cosmological dark matter sub-structure.