Most people on this forum have probably played quite a number of card, video and board games. There are a number of valuable mechanisms we've all seen in these game types that could be used to build a durable and entertaining tactical battle system -- in other words, totally unlike the snorefest of the HoMM games.
I'd like to say at the start that several of the games I use as negative examples are very good games, and several of the games I use as positive examples are very bad games. I'm not considering the games as a whole, just the specific feature I want to discuss -- and in my opinion, those games do the opposite to their detriment or benefit, without that changing the overall excellence or poor quality of the remainder of the game. Well, except for HoMM -- that whole series sucked.
The best board and card games have a limited number of extremely important decisions. A poker player can call, raise, or see on his turn. A chess player has six different pieces. The lack of microdecisions keeps players thinking about the interesting "big picture" issues rather than the limited and uninteresting stuff.
Huge numbers of poorly differentiated units and spells (HoMM and MtG) slow down battles/turns without providing additional "cool"
Guild Wars -- hard limit of eight skills on a player's bar, selected from a large pool of skills, keeps things interesting.
Armageddon Empires -- units have one or two abilities, battles are tight and tactically interesting http://www.crypticcomet.com/
Implementation: Limit the number of units per army, and keep their abilities to between one and three. No unit should require multiple pages to list their powers.
Automation is Essential
This is 2009, we've all got limited scripting experience (or the ability to google). Give us the ability to create macros for battles. Players who want to use chains of spells -- for instance, a weakening spell, a rooting spell, and a damage spell, all using different units -- should be able to predesign that chain and then push one button to cast it on the target. Players should be able to create and save starting battle positions for their armies to keep pre-battle fiddling to a minimum. In a word, allow players to automate the menial tasks while keeping control of the more interesting decision of when to use those abilities.
Negative Example: Starcraft -- zero automation, requiring players to devote a serious amount of time to simply managing these abilities
Positive Example: World of Warcraft -- skill chains are macroable, but still require player interaction to select the appropriate time and activate the skill.
Too Much Automation is Bad
Generally this is manifested in autocasting features, which act as a crutch for players overwhelmed by the necessity of managing tens or hundreds of units and their various, mostly minor, abilities. Abdicating control in this fashion to the machine loses out on a significant element of the game, and results in the player doing little more than attack moving and watching the game play itself. Avoid the sort of minor abilities that make this feature necessary!
Negative Example: Sins of a Solar Empire -- every ability is either machine usable or passive, with the vast majority of abilities (like the Advent frigates with antimatter thieving abilities) too spammy and fiddly for the player to manage
Positive Example: Empire Earth -- only a small number of units had abilities, and all of them were sufficiently potent that player management was not a chore.
Secondary Objectives are Essential
Most games have only a single objective in their tactical battles -- slay. This is in contrast to the huge variety of game types seen in multiplayer, where everything from resource acquisition (as a method of scoring) to capturing a flag (or princess) to holding a spot on the map for a period of time are included. Mixing things up in this fashion improves replayability and gives smaller armies a chance to turn the tables on larger foes.
World of Warcraft and Warhammer Online -- Both games have secondary objectives in their combat maps that are irrelevant to players as the benefit of going after the secondary objectives is outweighed significantly by the decrease in focus on the primary objective.
Rise of Nations: In the world campaign modes, many maps had secondary objectives, alternate objectives and all sorts of other activities. The sheer variety of these maps, and the substantive nature of the rewards obtained for pursuing those objectives, encouraged players to pursue them.
This is tied into the concept of broad decisions. Players should never ever ever ever ever be able to fit everything they need into a single army. Forcing players to specialize encourages supporting forces, and allows for players and the ai to deploy forces designed specifically to counter their army types.
Negative Example: HoMM (all of them) -- Everything you need can easily fit into a single force, and individual units can be expanded ad nauseum to essentially expand without limit the health and damage of units. Players are easily able to create functionally invincible armies after their forces reach a sufficient size.
Positive Example: Total War (all of them) -- armies are capped at a limited number of units, and the player cannot easily expand them into monstrous abominations. Even more important, the player can never create a truly unbeatable force, as sufficient numbers from supporting forces can be used to overwhelm their armies.
I've got a few more ideas, but I've spent a lot of time writing and, hey, it's not like someone is paying for all this crap!