I actually already have Gunstar Heroes and two of the Metal Slug games (the NGPC ones). I love them, though I prefer Contra's more serious atmosphere and H.R. Giger monstrosities... at least, that's what I'm in the mood for right now. Definitely gonna pick up the Metal Slug Anthology some time though.

And yes, Hard Corps has a story, complete with choose-your-own-adventure bits where you get different dialogue and story developments (and, in turn, different levels and different endings) depending on which choices you make. Granted, its still a kinda simplistic one, but I think its nice.

I've managed to get to I think level 6 in Hard Corps.