The city states would not have to be very large. Maybe half the size of the Dustari township, with walls, and densely built. The main ruler would have a township as well, so when his city states gain independence, he will still have something at least.
The baddy NPC's that people would have to fend off could easily be made. Just have respawning points for them all scattered acros the map, and have them attack city states. You don't need them doing any physical damage on the levels, because they would just make role-playing too hard and not fun at all

As long as these baddies harass people going in and out, that's fine with me.
I was thinking that the flag could have a black stripe on the top, and a white stripe on the bottom. This would represent the diversity of the kingdom that is unified under one banner. On the flag, maybe have the Graalian head or a single sword to further represent the idea of unification. City states would have their own small banners that they would have when they participate in wars with the main kingdom, and when they break off then they get their own flag.