I'd suggest
Land of Legends as a map. With 8 land nations, we'd get ~16 provinces each, Agartha would have no trouble getting its feet wet, and the map has an interesting gimmick: the central island has more magical sites than average, so getting in there nets you a) more magical gems and b) a dogpile.
ETA: although there's probably too much water in there if Agartha has free and unrestricted reign. Either we deal with it organically (by dogpiling Agartha), or by adding a 9th player as Oceania (a weak nation if I ever saw one), or, y'know, pick another map :}