It is very similar to both of those games, though. Metroid pioneered the "explore with a gun" genre, and Cave Story takes many cues from it, most of which eric noted.

The only comparison he made to Mario was the control physics, which are very Mario-esque, being floaty with lots of momentum.

I mean, what part of that do you disagree with? Does Cave Story not let you explore? Does it not have multiple weapons? Does it not have extra life containers? Missiles? Floaty controls? What?