I know there is a lot of replies, wondering if mine is going to be read. I decided to post here because I think it is the best place to talk about it. Here is the various factors you should consider:
Tactical VS non-tactical battles: Tactical battles has the desadvantage of being long, creates downtime in multiplayer and makes AI harder to devellop. But it makes combat more interesting and allows some micromanaging during the battle. First, I think the game should offer both options like in MOO/MOM, tactical or non-tactical. This way, you can speed up the game by using simple battles. I would even add the option to skip battles during the game if you want a fast resolution.Non-tactical battles could also be used as a temporary combat system for testing the game.
Second, since you can cast spell, even if you want to resolve battles fast, you need to be able to interfere. In MOM, you can't if you skip battles, it assume you cast spells. But for a non-tactical combat resolution, I would prefer be able to see each turn of battle where I can decide to cast more spells before clicking next turn according to how the battle goes.
Non-Tactical battles could be resolved "a la Ogre Battle". Units are placed in a certain formation and during the combat each unit target a unit by themselves according to the priorities (attack weakest/ strongest, etc) you have set. An Idea I had is to use the Infantry, cavalry, archery structure which I wanted to use in some of my games:
Archers attacks first but defender choose casualties
Infantry attacks second, but can only target ennemy infantry unless there is no ennemy infantry.
Cavalry attacks last but can target any unit.
This kind of combat system could be adapted to a computer game. The computer will choose the target according to the priorities. So the only thing the player would need to do is "Set Priority to attack and protect", "cast spells", click next turn, retreat or not, start a new turn.
For tactical battles, I think there is enough suggestions in this thread to make it interesting but you can still consider the following elements:
Army Structure: I presume armies are going to be structured by units. There are other structure possible like in Romance of the 3 kingdom (refered in this thread later on as R3K) which manage a number of soldiers which could be distributed in various units. Personally I prefer the unit structure since there is a so large variety of units.
Area Covered: Do you want the map to cover and area of the world (ex:territory), or cover the city and it's immediate surroundings. In most Civ types of games, Battles are focused around a city rather than a territory. In R3K 11, they had the unique idea of fusioning the tactical map with the world map which creates 1 big map that can manage battles and non-battle actions.
Map types: Everybody knows there are square and hex map. But have you considered the Graph Map ( a series of dot connected by lines). Units would move from dots to dots. You can also make joined attacks by making 2 group of units attack the same target. Graph map could also make the AI easier to design and make the combat faster to resolve since you do not have to move units individually, many times on many square. It also make the player focus on the resulting action. ex: I want to outflank my opponent, I make 1 move and it's done instead of making a series of moves to get the result.
Victory condition: How do you win a battle? That must be weird to say, most of the time, the battle are won when one side is destroyed or when 1 side retreats, but there are other ways to do this. For example, in shaterred union, you fought in an area which contained many cities and you need to control a certain number of cities in order to win. So the idea is that you can win without killing everybody which allows them to retreat and eventually retaliate. I also used the concept of tactical points that you need to capture in order to win. It's a bit like the capture HQ mechanism. Still in a fantasy game, some units like flying and burrowing units can make it easier to capture tactical points due to their high mobility or defense bypassing.
Leaders/Heroes: Everybody likes heroes, and besides questing, I think they would like heroes to participate in battle. I really did not liked how MOM managed heroes in battle because most of the time, it became a unit easily targetted which died easily. I think heroes should lead the battle and be placed outside the map of the battle. If you loose the battle, it could have some chances of beign captured. Heroes should give your army some advantages. You can give him passive advantages like all archers gain bonus, because he is better with working with that type of unit. You can give him some magical abilities: He protect his army from certain types of spells or give him special strategies (see next topic).
Special strategies: If you have few square/hex on the battle map or use a graph map, you could make units or leader have strategies which can allow units to attack and move in various ways. In R3k XI, there are tons of special move that you can use which makes battles more living. But if the map is too large (too much hex) planning the strategic moves becomes overwhelming (which is the problem if R3K XI).
Occurence: How many times will battles occur? This is important, especially in multiplayer for downtime, to know how much time a battle will interrupt the game. It is also important to know the quality of battles, are there few/lot of interesting/meaningless battles. In a game like R3K, Since invasions was from territory to territory, generally an invasion took place with a considerable amount of units and there was not too much battles which give and interest for other players to watch. But for example, in MOM, it happens many time where you have a few units spreaded on the map which happens to have a fight. It creates the problem of having many battles to resolve, which slows the turn, and makes them uninteresting to watch and manage.
This is all I have right now regarding battles. Hope it helps