You were talking about Mario Sunshine back there... Mario doesn't need a story. I think a Mario game should be pure gameplay... like a puzzle game but as a platformer... jumping from side to side... killing EVIL TURTLES and such. Very much like Sunshine's Warpzones. For me a Mario game should be more or less like that. Mario Galaxy is looking very much like that. Jumping from planet to planet... hitting turtles... etcetera.
Unlike Mario, Metroid should be more chalenging... going back and forth, sweeping the same place over and over loooking for and hidden thing, intense shooting, not too tactic, and it should have a cool story feeting it. I like the way how the story works in Metroid Prime 1. You're exploring the site, and as you explore you read what happened. Samus is space's Indiana Jones.