It's Ecco meets Metroidvania, with elements such as cooking/combining...
The biggest complaints have been some of the puzzles (Too vague), the combat (Too Hard) and the sense of where you're supposed to be going, but in making the game a more linear "Now Go Here!" (As Metroid will often do), you lower frustration but you kill the exploration element of the game.
I like Aquaria because it's something that hasn't been done to death: The 2D Undersea Exploration deal, and I was a big fan (Still am really) of the Ecco series. While it retains some elements of the Shoot-em-up and a bit of platforming on top of that, it's got a good selection of clever puzzles and scenery, and at the end of the day it was primarily done by two guys in their spare time, not a professional company.
Reguarding the comment about the gameplay being a glorified version of "Get Key and Open Door", you'll find that *EVERY* game follows this mechanic :p It's the simple 'Gate' principle of having to achieve something to proceed (If you've listened to the commentry on Half Life 2: Lost Coast there's a nice example of this - Defeat squad of badguys, Helicopter crashes into obstacle clearing it for you etc.), and you'll find Aquaria is one of the less linear examples - Whole areas of the game are optional, and several areas can be done in any order, the whole Food/Cooking thing is optional (but handy), optional bosses etc etc.
Also, your comment on the Gesture v HotKeys example from Darwinia? Aquaria already has examples of that. Obviously there's a few tweaks the game can still have to make things a little smoother but for the most part the only things I can fault are fairly minor (And mostly put down to the fact I never used the handy cooking system so just made things harder for myself until I stuffed Naija full of spicy food and decimated the final boss)
It's odd because one of the hugest complaints about Oblivion was the game constantly tells you where to go with a nice big arrow. Mods instantly appeared to kill everything on the map and have a true "Lost in the Wilderness" experience.
And yes, despite perhaps some loose influences with the art style, Aquaria has about as much in common with JRPGs than I do with Captain Pugwash.