Just like you want to have multi-tile cities, I think you should also have multi-tile armies. You would only get to stack up a certain number of units in one tile, and then additional tiles adjacent to that unit are required in order to increase the size of the army. You would define movement for the whole army by moving any of the pieces. The path algorithm would calculate the movements of each tile-group so that it arrived in the same adjacent tile at the destination location. It would also slow down the movement of large forces when travelling through confined areas such as a land-straight or between two mountains. The army would filter through one at a time, and the units that get through first would have to wait on the other side until the whole army got through before the whole group continues moving forward. This adds considerable tactics and strategy to the use of the map because creating choke points will actually let you slow down the movement of enemy armies. In addition, if you (for example) had flight units or mountaineer units and were sitting up in the mountains, you could launch a two-pronged attacked from a higher elevation on the army passing between the mountains. Your units would get a bonus to attack and defense for being at a higher altitude than the enemy forces. If the enemy army did not have mountaineer units or flight units, they would not be able to spread out through the mountains and would be extremely vulnerable to the attack.
For that matter, you could have it so that units sitting on a mountain tile could "hide" and not be visible to enemy units. It would consume any remaining movement points to initiate a "hide" action, but then your unit would be hidden until you directed it to move again. You could also do the same thing in forest tiles. Maybe you would require the unit to have a "mountaineer" or "forester" ability to be able to hide in those types of tiles. Then, an enemy army going through the region would need to scout the tile with a unit with mountaineer or forester ability to be able to detect the units. Once detected, any attack or defense bonuses from hiding would be nullified. The attack/defense bonuses for hiding would only be applied on the first attack, and maybe would just be gaining "first strike" and "negate first strike" or something. Coupled with any attack or defense bonuses from the tile, it would be a powerful combination.
You could then imagine having your army hidden on both sides of a valley and an enemy army coming between, you would direct your entire army to attack their army and you would get (for example) first strike, negate first strike, +50% attack, +100% defense. Your first attack would be utterly devestating and could even turn the tide of a war, just like in real life.
This would actually force people to stop and think about how and where they are moving their pieces and to actually start thinking like real generals dealing with real battles and real units.