When I was a kid I loved Stratego. I hate to admit this on a chess website, but I loved Stratego more than chess. A lot more.
But when I got a little older I discovered how tedious Stratego was if you attempted to play it at all intelligently.
Over the years there have been various redesigns. A thing called Ultimate Stratego wasn't bad. Electronic Stratego was pretty good too. Then, in the wake of the extreme success of Magic: The Gathering, they tried a collectible version called Stratego: Legends. That one sucked for a number of reasons. Then there were some themed versions, like Star Wars and Lord of the Rings. I don't know about those...never tried them.
In 2008, Milton Bradley (now owned by the megalith Hasbro) produced a version called Stratego: Ice vs Fire. If nothing else, this new version has some interesting pieces. These include the Dragon, Mage, Sorceress, and Yeti (yeah, Yeti). Not only is the Dragon the most powerful piece, it can also fly over any number of adjacent pieces and attack on the same turn. The Mage can force your opponent to reveal a piece up to two squares away. The Sorceress can require an opposing piece to join your army. And the Yeti attacks all pieces in adjacent squares simultaneously.
One strategy you might try: Sneak a sorceress into your opponent's territory, enchant a dwarf to join your army, then attack your enemy's traps with it.
I've only played Stratego: Ice vs Fire a few times, but I thought it opened and speeded the game quite a bit. I'm not sure the changes increased the tactical or strategic depth, but it at least gave me the incentive to revisit this old game from my childhood.