Really I think it depends what you mean by underdog. Frogboy made a great post about victory conditions a while back (sigh, I can't find it...). But to summarize, one player might have a unstoppable military, and it looks like it's only a matter of time before the entire world succumbs to it. But another player might be well on his way to casting a major world-wrecking spell that will completely change the game - the player with the unstoppable military might topple over, indeed most empires would probably suffer huge damage, leaving the caster of the spell in a very good place. And yet another player might be well on his way to completing his Master Quest, snatching victory from both the military superpower and the magical destroyer. And who knows what other victory conditions might be available.
I think that's the best way to handle the 'underdog' problem. Make it very difficult to tell who is actually an underdog; if a powerful empire sends a huge force to roll over a smaller, seemingly innocuous nation, maybe just before the killing blow is struck to the smaller nation's capital city, the defending channeler will utterly destroy the invading army with the culmination of a powerful spell that has been a long time in the making. But at the same time, if you (or any other player, human or AI) are on the losing side of a struggle and have no tricks up your sleeves, the game should definitely not come and save you. Basically - if you are straight up inferior to another nation, it should be quite a challenge to defeat said nation.
Basically, I think that providing many options with which to handle a situation is the best way to make underdog scenarios less clear. You shouldn't necessarily be doomed just because the nearest military superpower has declared war on you - you may not being able to match it militarily, but maybe your magic or allies or something else you've been preparing can save you; and these means that you never were really the underdog - it just means that instead of focusing on military might you focused on different, but equally important, aspects of your empire.