Well the solution is as obvious as it is simple (in fact I've already seen it on the web !)
Simply subtract the normal initiative penalty from the characters dexterity attribute when figuring out movement stats, do however not include the shield's penalty.
For example Crougar, the human warrior, has a dexterity value of 16, which gives him a basic (nude) movement of 75/38; if he is wearing his standard suit of plate mail armor, his modified dexterity is 12 (16 minus 4), resulting in a new movement rate of 57/29 !
Author's Note : If you take into account "real life" (NO, I don't mean the MTV series), subtracting twice the initiative penalty would come closer to reality.