I usually win with the spell of making. My approach is to start early with trade agreements so the other factions tend to be friendly towards me. I usually build a very small military for defense and helping my sovereign/champions. Once an opposing factions starts getting too powerful, or starts acting hostile, I set all the other factions to war against them (which I can afford since I didn't buy and don't have to maintain a large army).

When they're all fighting each other they're using massive resources, which gives me an edge. Even if one does declare war on me, they are usually too occupied by all the other wars to pose any real threat. At this stage I usually start building the towers needed to cast the final spell.

I have played several games now, and in none of them has military been my primary focus.

My initial "learn how to play" games were civilization based (zergs ftw!) but I went for the quest ending -- storm dragon camps made this easy).

And then I played a large random game with a mage sovereign (where I cloned Pourpupine and tweaked a few things), and in that one, I had no champions and a small and useless army, and once I learned how to play in that style... nothing has a chance.

Anyways, here is my take on the victory conditions:

Military: I like this victory condition because it lets me play for a long time without worrying that the game will end too soon.  The AI has to defeat me before I can lose.

Diplomacy -- I worry with this one that if I enter into any diplomatic agreements that the AI might complete this before I.  Quite likely the game has been designed to prevent this, but to avoid that possibility I play with this turned off.

Quest -- that was interesting, but mostly you just need to build up enough strength, and then it's easy. Perhaps though there are secrets in the game that allow for differences in quest progression and story?

Magic -- this is way too cheap.  My civilization sovereign found the magic victory condition cheaper to build than one high-end company.  So I have ignored this victory condition and routinely disable it (I probably like playing the game for a longer period of time than this victory condition was designed for).

Anyways, the AI seems to have an early game advantage, but because of how effects compound I think we have an advantage if we can survive long enough to get good force multipliers.  This makes, for me anyways, starting near a military AI sovereign a ruinous event, while starting near anything else seems to work well for me.

The AI may think that it has a stronger military than you but the reality is that if you have an ungodly supply of mana, no army can beat you.  When an opponent becomes a threat, you wipe out their cities with volcanoes.  It's messy, but effective.  Much better than Terror Stars in GalCiv 2.

It seems, according to your post, that the "stack of doom" game mechanic itself isn't what you have a problem with...it's how the AI uses them.  

i think stacks of doom are far less of a problem here, than in other games The strategic spells allow you to scupper them pretty well, and the city defenders that respawn at full health after every battle help to offset being worn down.

I never have to USE stacks of doom, certainly. A few decent champions can hold off massive armies, single handedly. And magic is powerful enough to wipe the battlefield in a single spell, sometimes.

'Zerging' in RTS as a strategy is usually a terrible idea. Unless you are playing Zerg (still don't recommend). Early attacks is perfectly viable, especially if you have better macro than your opponent and you can build up faster, and they can't manage the damage you're doing. Rushing often ends in a loss if it fails (Rush = All in straight away).

The problem with calling armies in FE a 'stack of doom' is that they have a limit. And you need to research to increase that limit, you cant just build 30 militia, put them in a stack, the click approximately on your oppoents capital and win. If your opponent has a big army, you too should have a big army, else you're asking to get your ass mass handled to you. Not to mention the cost of treaties, god damn. Design your army to counter your opponent's army (an RTS tactic you should be familiar with), so when they clash you come out on top, time and time again. If you don't like the idea of mass producing units to fight off stacks of doom at heavy losses build a defensive army, take life magic or to manage your army better in battle.

Building units wastes precious infrastructure time. Call to Arms  .