There are some excellent points here, so first off, thank you for your input!
Your synopsis of what games are similar to ours is very accurate. Our original thinking was, take the core idea with Warlords, and then add as many features and depth as possible while also being able to deliver it in a super streamlined package. To be honest, I just really wanted to play a game of Warlords with more stuff)
As far as combat, The ideal situation would be to lower anxiety, and raise the player's knowledge of what is happening on screen. I agree, when a player just kind of watches something unfold, without knowing exactly what is happening, it creates an unpleasant tension, and worse, resentment that the relevant information was not delivered in a more plain way before the battle even started.
At its core, the combat system is actually a pretty simple, and the calculations for who wins what combat is also fairly simple, but currently we have not delivered the player that information.
The REPLAY idea is interesting, and may be an excellent way to deliver this information.
As a new player, I would learn a lot from this. The game starts off simple, and the replays could convey simple information. As battles gain troops with more abilities, those abilities can be explained in more detail, and the player can reply to watch more closely how these things play out.
Honestly, I totally forgot other games do this and its a solid idea and I appreciate you bringing it up.
Once you know what is happening in the combat, the anxiety of not knowing what is going on is replaced with a much more pleasant anticipation of seeing how things turn out. But I agree currently we are not there yet.
A game that I feel is similar to this is Super Auto Pets. Before I played the game, the combat looked insane to me and impossible to understand. After a while they started to make sense, but we have got to do a better job getting players to that point in our game.
There is actually some room at the top and bottom of the combat popup. I can try to do a sample battle with information that pops up during the combat to describe what is happening. 
I hope you check back and see how we apply your feedback, and thanks a lot for sharing!
I did some thinking about a potential replay function. Here is a very primitive mockup of a button that toggles open a menu.
The lower controls could let you do stuff like replay, choose the speed of combat, or even pause and move forward or back a step? The controls could be more or less granular.
I didnt put a pause button in this mockup, but in order to read what is happening in the top part, a pause button may be required.
The top section tells you what is going on in greater depth, and if any keywords show up there, you could click on those to get further information as well.
I guess after the 100th combat you would probably toggle the information and controls off, but it would be very informative in the meantime)
The main thing, besides the toggle button, controls and description area, would be the fact that you would have to click a button to confirm when a combat is done. This would be required, because when I am playing and a combat goes by that I was like "what the heck jus happened?!" I would want the option to hit replay at the end of combat to get a closer look.
Would that button be so bad after every combat? Probably not, but it would slow down things a bit. Maybe thats a good thing.
Another way to get more information of what is happening during combat may be to announce the damage done by an attack or ability.
The information goes by very quickly on Super Auto Pets, but they do announce the damage in big red numbers. If 3 Mages cast a fireball in KH, it would maybe be nice to see that damage number.
... and, I never noticed it before, but SAPs has a few replay control at the top of their combat screen. I might prefer the buttons under the combat tho, closer to where the mouse or hand is usually resting.