AurelianDragon: Movement speed is a function of base armour type, magicality of armour, total encumbrance carried, and Strength.
* All armour heavier than leather limits your movement to some degree, to either 9 or 6 squares max depending on the armour type.
* Magical armour allows 3 squares better movement than nonmagical armour of the same type (but not higher than 12)
* Encumbrance thresholds gradually limit your movement to 9, 6, or 3 squares. These thresholds differ depending on your Strength score.
* Boots of Speed double movement, AFTER the above are all considered.
* Potions of Speed and Haste spells also double movement, AFTER the above are all considered.
* The boot effect stacks with the Haste/Potion speed effect, but Haste and Potions of Speed do not stack.
* Certain considerations (only seen in certain Gold Box games, most notably Dark Queen of Krynn, Pools of Darkness, and the Savage Frontier games) can reduce your movement rate still further (to a minimum of 1).
Your Fighter/Mage's Plate Mail is presumably magical, which explains why you're getting a movement rate of 9 (Plate Mail base movement 6, magical armour +3 movement bonus).
Your Fighter/Thief is encumbered; his Strength score is low and/or he's carrying too many coins or arrows (you mention he's not carrying "extra gear" but you may be overlooking money, and too many arrows will weigh you down also).
Thanks for the feedback. I didn't know magical armor gave you better movement. That's good to know. Okay this is what my fighter/thief is carrying:
This is it. He's carrying no money at all and none of these items seem like they would be heavy. When I unequip the chainmail my movement goes up to 12.
UPDATE: I traded everything he was carrying to another character except the chainmail and his movement is still 6.