Here's how I'd make it more intuitive.
Axemen -> Rocket Troopers
Lancemen -> Tanks
Swordsmen -> Infantry
Units of different kinds can't stack, as stacking both makes things more complex to display (so less intuitive) and reduces tactical complexity by blurring the lines and allowing general-purpose forces.
- Squares and circles all become Towns. If a unit starts and finishes a turn on a town without splitting off units, it gains 1 strength up to the maximum.
- Triangles become Flags or Towers.
Mechanically, here's what I'd change:
Armies have a maximum strength of 5. You start with one army of each kind, of strength 3, in one corner of the board at (0,0), (2,0) and (0,2). (If the maximum/starting strength is too high, then splitting off single units to capture stuff becomes too safe.)
Each turn, players may move all or part of every single army they control. (Moving one at a time makes the game less interesting by preventing coordinated actions, while also making AI writing more complex.)
If an army moves into a friendly army's location, they swap places.
It takes five turns to capture a flag/tower. (This is so that, if someone rushes to capture flags too quickly, the opponent can take a few turns to reinforce/get into position and then guarantee winning the fight.) Once captured, a flag/tower remains yours even if you move all units off it.
The flags/towers should be spread out, not concentrated in the centre. I'd have three along the diagonal of the board (at 1,1; 3,3; 5,5). Spreading them out and making it take a while to capture something makes it harder to rush in for the win (your 'puma') and harder to have strong armies hovering around all of them at once.
Win condition: Every turn, each army occupying a flag/tower that you've captured gives you 1 point. The winner is the first player to, say, 20 points.
Combat mechanics: Defending units do damage before attacking units. Armies do 3 damage to the kind they're strong against, 2 damage to their own kind, and 1 damage to the kind they're weak against. Defending units take no damage if they kill the attacking unit. If an attacking unit destroys a defending unit, it moves to the defending unit's old location.
(Optionally: A unit can only defend against one attack per turn. If an army of 5 tanks is attacked by rocket troopers and then by infantry on the same turn, it does 1 damage to the rocket troopers and 0 to the infantry, while taking 4 damage itself.)
I'd also reduce the number of towns substantially to 4 or even 2 on each side. (Not 3. The number of towns should force you to unbalance your army.)
With this set of mechanics, I think you have to react to the unit types your opponent is making more of, rush to capture points ideally just before your opponent does, and play tactically to win combat. I'd have to prototype to figure out if it's a good direction, but it feels a bit easier to get a handle on and I think it definitely has interesting strategic problems in. I mean... it's really easy to see what's going on here, right? But... what's a good opening move?