I actually kind of like the concept of "having to pay to unlock" upgrades as a way of implementing the things you've observed in combat. The tall-versus-wide dichotomy is a strategy concern worth preserving. And speaking of busywork, given that it's a choice of upgrades, I'd rather not have a zillion of those "pick an upgrade now" screens right after a major battle. And you can always conceptualize it as buying better armor, or the experience prodding you to realize your vulnerability in an area and seek out a trainer to deal with it (after all, it always seemed a little artificial to me that "I've just beaten up 10 giant rats; now I have developed the ability to summon fire elementals" is the default for a lot of games).
It might be better to keep the "pay to upgrade/train", but have the trainer "accompany your army" (i.e. be a button that is usable anywhere), rather than have to return to town/wherever. That would seem the best of both worlds, and maybe allow for some interesting quest ideas to play around with.
It might be better to keep the "pay to upgrade/train", but have the trainer "accompany your army" (i.e. be a button that is usable anywhere), rather than have to return to town/wherever. That would seem the best of both worlds, and maybe allow for some interesting quest ideas to play around with.