I played in similar settings, though I used Very Hard rather than Legendary.
Playing as Settra, you won’t really have too many issues with public order I found. When it comes to dealing with armies, focus on getting your high tier buildings as soon as you can. I also typically ran my armies around in pairs supporting each other. I hate doom stacks, prefering instead for some theming, especially with the generals the game gives you via research. I normally had one army with skellies, and one army that was a little more specialised with Constructs and artillery. They’d back each other up and really helped with the general expansion. I found mid game opened up once I had screaming skull catapults. Casket of Souls is ok, I think it got buffed recently.