When I was I kid, we were really into this game, and came up with some variants which would probably not be too hard for you to add as options (ok, apart from the AI...!), if there's any interest.
We had moving bombs and flags, which really changed everything. The bombs would function as normal, except they could also attack (they might be seen as armored units, to accompany the infantry), and the flag would be as defenseless as the Spy. (It would win only against the other flag, if it was the attacker.)
We also rotated the board 90 degrees and set up the game pieces so that one team would originally occupy (from the perspective of the standard board orientation) on their own side, columns 8 through 10, the rightmost neutral area, and on the other side, columns 5 through 10, with the neutral areas being one's own column 7, the central neutral area, and the other side's column 4. (Left-handed people may want to flip the setup, so that the safest corner is on the lower left instead.)
Then we tried "Mixed Stratego," with the same moving bombs and flags. We would each get a flag, and everything else would be chosen at random. The teams were often not fair but we weren't all that bright, so this didn't matter much. Each side's colors not being uniform just added to the craziness. I wouldn't change this "feature," if it were my game!
Also, the original rules required that the scouts stop in front of a piece and attack it the next turn. I'm probably not the first to bring this up.
http://woz.commtechlab.msu.edu/courses/ ... rules.html
"The Scout may not move and strike in the same turn. "
Maybe the rules have changed, but it would be nice to see this added back in as an option, unless I missed something.