The only planet you destroy in Metroid is Zebes, and that is a cinematic.
Tcjudas, you're describing a basic roleplay game. An over wold, that comes encounter with a (in this case planet) and then you go to a battle screen, correct?
If so can you describe the over world a bit? Did it look something like this?
Yes It looked like this. That picture reminds me of that game, the game map is similar to this and have almost the same planet layout but it isn't the Legend of the Galactic heroes neither
As i said earlier you start with a spaceship and there is a map on the right so you are trying to find planets on the map and the map tells where you are you can change the direction of the spaceship you can't choose the planets automatically you have to fly to them by yourself(you see the spaceship above like Star Soldier and the map is cutting the screen 1/3 so you can see both the map and the spaceship seperately), while you are trying to find planets in spaceship, you can't see more than stars on the background and the spaceship. There is a map on the right of the screen that tells you where are the planets are(planets are shown as the big dots) and there is a random chance of encountering with a enemy spaceship, the game world is so huge and when you reach the corner of the map you continue to move on the other corner so there is no end of it. the game was amazing, encountering with enemy ships was like final fantasy game fighting style but not completely same .It is something like Rpg in space. When you encounter a planet, it shows gravity and things like that, On that screen if you press start you fight against that planet and you play as a robot(the robot is tall and holding gun like megaman and it can only shoot bullets), you can only jump shoot and move directionally. You have control in mid air it is alot like Contra when you are fighting against a planet, there are moving enemies and turrets that shoot bullets to you, its side scrolling shooter but you can't scroll the screen by yourself, the game scrolls automatically so you can move to end of the screen. Every planet have its own atmosphere. There is not much left to say about that game.