Besides having new playable races, why not have some unplayable ones too?
For one, I'm thinking more human cultures. There could be nords up north, and middle-eastern civilizations in the south. These can be affected by the more important races (like what if a large part of the middle eastern kingdoms had been conquered by dragons? Or if the nords were raiding the coasts of Teria and the elven lands?).
For other smaller races, maybe stuff like minotaurs and centaurs (I'm thinking of having them just north of the desolate hills; maybe the weird magic there created races of half-animals?). Or maybe mermen in the western oceans?
But all should have a number of units unique to them, which could either be hired as mercenaries or bought with influence. And, generally speaking, they should have their own regions and their own cities that you eventually can siege.
Just an idea.