Use the Worms Blast style, it was awesome, with 3d celshading on 2d! Something like new mario bros..

And how about land underwater? The worms could be able to swim for a couple of rounds or so, with some divinggear, and then drown. There would be treasures and perhaps bubbles of air underwater.. Perfect for a darksider..

Or you could have boats.. You can use the boat and attack in the same round, but would be stuck in the boat until next round. (easy target) Perfect for the lightsiders..

There could be a captain of each team (use the characters from blast, and some new ones) If there's two similar captains, one of them would change colors or something.. The captain has extra life and a special attack/move..

And this idea is a bit crazy, and perhaps impossible to make in the game: What about binding another worms in a ninjarope, by shooting it on him? (or perhaps a chain..) the other end of the rope would stick to the place you shoot it from. (end turn) the worm wouldn't be able to move longer than the rope/chain is, and, if it falls over a cliff and the rope's not long enough, would hang and die, or loose lot's of health every turn. This opensfor a new possibility: Tie up a worm, then shoot him (in the next round if you're still there) he will fly, suddenly stop, and loose loads of health.

And this idea is a bit crazy, and perhaps impossible to make in the game: What about binding another worms in a ninjarope, by shooting it on him? (or perhaps a chain..) the other end of the rope would stick to the place you shoot it from. (end turn) the worm wouldn't be able to move longer than the rope/chain is, and, if it falls over a cliff and the rope's not long enough, would hang and die, or loose lot's of health every turn. This opensfor a new possibility: Tie up a worm, then shoot him (in the next round if you're still there) he will fly, suddenly stop, and loose loads of health.
Hmm... that's one I didn't hear before...
Although it would be too overpowered! The closest equivilant would be tail nail, that stops a worm from walking, but that effect goes away as soon as the worm is hit with an explosion.