Three TBSs come to mind. Well, four, but I have no experience whatsoever with the fourth. All are quite capable of running on older machines, though in HoMM's case you'd have to look to an older version for that.
Age of Wonders
Age of Wonders: Shadow Magic is a TBS with both empire-building and relatively small army battles. It's a bit limited in both cases, though; the empire building is more upgrading your cities and occasionally capturing or founding new ones, plus seizing resource nodes to boost your empire's production.
Units move overland in stacks of up to 8 units on a hex grid, which switches to a still-hex battlefield map when two armies fight. Any force adjacent to the fighting stacks is pulled in, meaning you could theoretically surround a lone stack with six stacks of your own. In practice, stacks of around three per side are the biggest that are routinely feasible.
Units can level up, but only to silver or gold medals, gaining a respectable but not huge bonus to stats and usually special abilities of varying special-ness. Heroes work slightly differently, manually selecting their benefit (a stat boost or special ability) each time they level (which is more than twice, obviously).
Also, you play as a wizard, so you can do wizard things. You research spells, which can then be cast by yourself and any heroes who happen to have casting skill. Heroes can only cast in battles (or stacks, in the case of noncombat spells) they happen to be in and are usually worse (less mana to spend) at it than you, who can cast it anywhere in their domain. Your domain is a big area around you which gets bigger with certain skills and buildings, as well as a small radius around every one of your heroes, assuming you have a tower in the city your wizard is in (also note your wizard can be killed like any other unit, but respawns in any wizard tower you control at the start of your next turn; if you don't have one, that's game over). Spells range from persistent overland effects to permanent summons to direct battlefield attacks, plus overland attacks, persistent unit buffs, healing, debuffing attacks, whole-battlefield effects, and so on.
Master of Magic?
I believe Master of Magic is sometimes described as being similar, but I'm sadly not familiar with it.
Heroes of Might & Magic
The Heroes of Might&Magic series is similar, though, and I can describe that one vaguely. It's similar to AoW in that you run around an overland map, using a hero to lead an army in ambushing random creatures and collecting stray resources, but armies work completely differently. Instead of a given number of individual units, you just have a mass of X creatures represented as one said creature, which then hit and do special abilities in proportion to their strength. This also means damage can reduce a stack's effectiveness, since it often involves creatures dying.
It also features magic, but I believe this is entirely limited to heroes, and I'm less familiar with how it works.
Warlords
Finally, there's Warlords. I'm sadly only familiar with 4, but it's very vaguely similar to AoW or HoMM. The biggest differences are that cities are very, very common and that there is no strategic battlefield- during combat, you can cast spells if you've got the mana, but otherwise simply shovel your choice of next unit onto the battlefield, where it fights to the death, at which point whoever lost shovels their next unit on or the battle ends because everyone on one side is dead.
Magic is cast by the Warlord- the player- but tends to be somewhat limited in number. You won't be casting spells every battle, usually.
Cities function considerably differently than in the other two games. First of all, cities are common, and serve only two (well, three or four) functions: One, they produce units. Two, they produce gold. They're also fortified places to withstand an attack in and can be near enough to special overland buildings to claim their bonus for you. Producing units costs nothing but time- they simply require upkeep once existent, and more advanced units require cities to be of a given level to be available (leveling a city up costs gold and is the only method of upgrading them, other than razing other cities so they're the closest to an overland bonus structure).
Units also function differently. For starters, it's expected that you'll burn through them like there's no tomorrow, even though each one is a discrete unit with its own suite of stats. Secondly, the can level up repeatedly in identical fashion to heroes- it's just, as you might expect, rather rare and not particularly valuable for most units. Heroes, in addition to having nice stats and the ability to equip items, are good for armies because they have- depending on alignment- a skill to improve their own stack or hamper an enemy's stack.
Apologies if these are a bit rambling, I wasn't sure how to describe them in a more codified fashion.