What sorts of titles are out there and what are their strengths and shortcomings?
On a nit picky note, do we really have any at all? Even Majesty, which is literally subtitled the the fantasy kingdom simulator its more of a city simulation than a kingdom one.
I've noticed that there tend to be more historical games than fantasy ones. There were about a dozen historical Impressions city/nation sims, depending on map size. Then there are a lot of Roman ones. Majesty is probably the only magical one. Even DF, in so far as its tangentially related doesn't really do magic.
We have a spate of minecraft inspired voxel type city simulators like Timber and Stone and Stonehearth. Banished may or may not be able to support several cities.
None of those has any magic. I've always wanted some more straight fantasy games, with various magical systems. But I'd also like some sort of magitech or steampunk game and possibly a magical-industrial complex game. I always wanted to play something like the Velgarth Eastern Empire with magic integrated into industry.
And we definitely need some sort of adept level mage or magical academy focusing on spells vs integrating low level magic and/or high level magic into the mundane economy.
Many city/kingdom builders tend to lack combat at all, like Impressions games with only superficial fighting. Others lack any sort of variance in both magic and construction between games. That is, there are no significant developmental decisions. On various city building forums many complain of the lack of variation in cities. Its come up a lot in regards to TiltedMill(some impressions employees) as they work on Medieval Mayor.
Majesty does not have a very deep tech tree. There are only a dozen heroes for instance. As someone who is really into Dominions and Warlords Battle Cry I like to have metric tons of unit types possibly with multiple upgrade paths.
Off that topic, who knows of cool or unique kingdom simulation games? Crusader Kings might count but I am not including Total War or Civilization style games since they are either highly abstract and/or turnbased or they focus too much on combat.