Oh man, I loves me some Fantasy Generals. If you're new to the game, by all means take either Calis or Marcus. Their troops are beefier, and you don't have to muck about with magic.
A few words about strengths and weaknesses of each character:
Knight Marshal Calis
Pros: Lots of good cavalry troops available, decent infantry, somewhat weak ranged and siege units. Has a healing spell that can can be cast once per battle, to save a crucial unit. Most units can be upgraded.
Cons: Little access to nonstandard attacks (magic, mechanical)
Lord Marcus
Pros: Great infantry, good ranged units, decent siege and cavalry units. All units can be upgraded.
Cons: No magic, no nonstandard attacks
Sorceress Mordra
Pros: Access to a number of beast units, which are typically tougher than their standard counterparts. Limited magic during battle (one plague and one healing wave). Randomly summons a handful of extra troops at the start of each battle.
Cons: Most units cannot be upgraded. Summoned troops disappear after battle.
Archmage Krell
Pros: Access to a number of magical units, which take less damage from normal attacks, but much higher from mechanical attacks. Can cast a battle spell every turn.
Cons: Most units cannot be upgraded. Vulnerability to mechanical attacks becomes a serious problem once those units begin showing up (2nd or 3rd continent, IIRC).
The inability to upgrade most of the beast and magic troops is a considerable hindrance as the game goes on. They can gain experience, which makes them more potent, but a 1st-tier heavy infantry with max experience is still not as good as a 4th-tier heavy infantry with no experience. You can still research better tiers, but will have to settle for recruiting new units instead of upping those troops that have been with you from the start. Krell's magic can be a major factor, but I find it's quite easy to forget to use it each turn.
If you play as Calis or Marcus, what you'll wind up with is an army that you try to conserve, so that you have a core of top units that you build up throughout the game, upgrading and adding items (and if you're like me, even renaming to make them unique and identifiable).
If you play as Mordra, you'll be much more cavalier about troop losses. You'll still want units to survive so they can have higher experience, but the lack of upgrades and the handful of one-time troops you get each round mean that individual losses aren't as big a deal. Your magic is potent, but limited and needs to be timed well for maximum effect.
If you play as Krell, you're as big a factor as your troops. Like Mordra, you're less concerned with individual troop losses because most of them can't be upgraded. But you don't get free troops each round, so you don't have cannon fodder. You also have to worry about mechanical units (although it should be noted that just as mechanical attacks do more damage to magic units, magic attacks do more damage to mechanical units). If you can find the Artificer during the course of play, you field both mechanical and magic units.