This reminds me of the game "SPORE" in the last stage, you flew around in a spaceship conquering planets. The game had a balance problem, but while the space combat was difficult - it was rather easy to fly around a planet really quick "Terraforming". Remove the entire atmosphere, then add the atmosphere back and plant a colony.

As a bonus, the other aliens in the game didn't view destructive terraforming as equivalent to WMDs - you could do this without even declaring war.