Move PMed.
While I think soldiers might be a little overpowered at the moment, I don't think making them more annoying to play(which is all reducing the movement does, really) is the solution. Considering that movement is far less useful than in the original game, simply due to the turn based mechanics, I don't feel like that's the best solution. Don't think they were that slow, either...
Giving them a bigger accuracy dropoff, nerfing Explosive a bit more or removing the ability from Rocket launchers, giving them a damage dropoff, or possibly reducing their health would all be possible solutions. The only difficulty right now is that Soldiers can simply sit and shoot everything, and since movement doesn't factor in, you can't avoid their rockets by being fast, like a scout.
But a lot of these problems, soldier, engineer, heavy, all probably come from small map size and small range to match it. On a bigass map, with lots of open space, but still close in quarters, choke points, blind turns, etc., engineers could build, even using their health, and have enough time to make something useful before the enemy arrived, snipers would be worthwhile at all, heavies could 'set up' at choke points, scout's movement would be worth a damn for finding the enemy, etc.
Hell, one thing you could do, if you increased the map size, is make it so rockets moved towards a specific square and then on in a straight line, over multiple turns if the target was far enough away.
Stretching out initiative steps would work too. Person to roll highest moves, then the next, and so on, and then things are built, shot, or reloaded. Or vice versa, or even you choose which(so if you roll higher, but want to shoot after moving, but they want to move before reloading, just around the corner of a wall, they'll still be able to 'dodge'.
Always difficulties with translating an Real-Time game to turn format, is all.
Edit: Actually, just figured out really simple way to implement movement into accuracy. You can go about this one of two ways; If you're shooting at someone, subtract the number of squares they moved away or sideways(coming closer doesn't really degrade accuracy, though you might make it count for scouts or something; maybe jumping will count as movement like that) compared to you(total movement, no swerving back and forth, at least in this, whilst repairing your turret >.>) from your accuracy roll(also, compared to you, so if you're a soldier and move three spaces, while the scout moves in the same direction, but five spaces, it counts as 2; nice job predicting his movement). Or, add the number of squares they moved to how far away they count as being. Or one half the number of squares they moved, rounded up. This wuld be sentry guns would be a little more vulnerable, being stationary, tanks would be comparatively easy to hit, scouts would be a pain in the ass, etc. The flipside of this is that moving should apply half the same penalty to hitting any targets you are moving sideways relative to; strafing is beneficial for your health, but bad for your accuracy. Retreating is always good for your health.