Raptors might be useful, at least until storms are around -- they're cheap in both gold and resources IIRC and provide a slightly useful raiding force.
Amazons and druids provide magic which might not be readily found on national mages.
The Hidden Kingdom of Elludia and the Grey Tower are two magical sites to take a gander at.
Shamblers let you go underwater, and Tritons let you defend your new holdings more easily.