As many have noticed, a lot of platformer indie games have come out in the past year or so. As such, it seems like there's a large chunk focusing on being puzzle platforming, rather than being the action/adventure styles that I enjoy most. I prefer games with a good story focus. I'm looking at possibly getting some games in the upcoming sales (steam, GOG, Desura, etc)... so here's my question for you:

What platformers do you recommend that are not considered "puzzle" ones, but rather are Action/Adventure focused?

Additional info:

Some games that I would throw in this ideal category would be: Treasure Adventure Game, Cave Story+, Super Panda Adventure; All of which I couldn't stop playing til I beat them. Rogue Legacy is great, but it is more of a rogue-like action than it is "Adventure". Braid was mediocre and too "puzzle" oriented for this, though the gameplay was unique to keep me interested til I beat it. I've tried La Mulana few times and couldn't get completely hooked. It seems to be lacking in story development (though I only played for a couple hours total).


***Edit- to add more examples

There are some pretty good platforming action/adventure games here on GOG. Just to name a few, the Trine series, Realms of Chaos, Duke Nukem 1&2, Duke Nukem Manhattan Project, Spelunky, and La-Mulana.

Rayman Origins is the first thing to come to mind, although it's not story oriented and you're probably already aware of it.

The Apogee/3D Realms games:
Realm of Chaos
Hocus Pocus
Secret Agent
Duke Nukem 1+2

The Dangerous Dave Pack

Dust: An Elysian Tail (you might like this one the most)

Superfrog

Capsized

Earthworm Jim 1+2

Mutant Mudds

Rayman Forever + Origins

Guacamelee + Mutant Blobs Attack

Unepic

Valdis Story: Abyssal City

Volgarr the Viking

Annnd my personal favorites: Oddworld: Abe's Oddysee and Exoddus, which are puzzle-y, in a way, but not to the extent of, say, Braid. It's more about trying to keep yourself and your fellow Mudokans (the race/species/whatever of your character) from being killed by everything around you. Oh, you get to possess enemies with guns too sometimes, that's always fun! Plus they have great stories/cinematics too, which is part of what you're looking for so that's a plus right there.

And on Desura you should check out Oozi: Earth Adventure (also on Steam now).

Anyway, I highly recommend Valdis Story: Abyssal City. It's rather short (about 20 hours for me according to Steam) but I left out two optional, incredibly hard bosses along with some optional but hard-to-get items. Still, it's worth it.

Unepic is also great, especially after you meet your first "companion". The end game is not the best though.

Guacamelee has a solid and consistent combat system and weird but interesting theme.

Megabyte Punch is Mega Man-like, you get weapon power ups by bosses and you can combine some few items. I played for a few hours after I purchased it at IGS but I found a certain move that made me invincible and I lost motivation to play after that. Still recommended.

La Mulana is awesome as long as you can keep a healthy flow, that is troublesome sometimes with the frustrating combat and puzzles. I would say this is closer to a puzzle roguelike than an action-adventure platformer but I suppose it's rather a good mix between them all.

Check out Fez. Open-world exploration, some puzzles, item gathering, platforming - it's definitely falls into the action-adventure category.

Trine seems a lot more puzzle-focus rather than broader adventure, but it might be fitting. I bought both games recently, but not played them yet so I'm not sure.

I'm planning to buy Rogue Legacy and Spelunky tomorrow but Rogue Legacy is action-RPG as far as I know.

In a recent Humble Bundle I bought included a game called Capsized which might fit your description(sorry haven't played it yet either). It is here on GOG too.

Duke Nukem games is mentioned here. I fail to see how that is action-adventure. Platforming + run 'n' gun shooting. I don't see any adventure elements. Strictly linear, no exploration, no open world, no puzzle solving - it is pure action as far as I can tell (I haven't played them).

If you have Wii or Wii U check out Super Metroid. Still the best sidescrolling action-adventure out there, simply a must-play for any fan of the genre. The Castlevanias for DS and GBA are great too. Just in case you haven't heard of these game, maybe you have.

Dust: An Elysian Tail is a clear recommendation. Although the game stresses the hardware a bit in the end-game phase, when there are lots of opponents. Be sure to have good cooling and no overclocked configuration.

SpooferJahk nailed it, Duke Manhattan Project, hands down and without question. I am not a big platformer guy but I adore this game. It's fast, simple, loud, bloody and looks amazing. There are great 3D-esk sequences that are traditional platformer but, for example inside of a silo, so the screen turns with you as you go in a circle.

Also, hot chicks tied to explosives to save! :D

I mean, we have the first five Tomb Raider games here.

Also, Beyond Good and Evil.