You must not have played much of the game if that's all you remember. Lets see, you had to solve the puzzle to get through the forrest to the graveyard. There was the puzzle about how to get into level 7 where you had to play the flute at the pond. Burning bushes to open up secret areas, also blowing holes though walls, pushing blocks certain ways, the endless maze through Death Mountain, figuring out to feed Digdogger the meat...
I think that's a little different than just running to the end of the level dodging bullets and shooting bad guys. Of course Contra was an awesome game in it's own way.
I'm sure you didn't grow up with Zelda so it's not a big deal, just the first time I ever heard it referred to as a shooter.