Cave Story +. Seriously, it's quite amazing and has a great soundtrack too.
Seconded these, especially as they both have great soundtracks.
A few other Metroidvanias that haven't been mentioned (and might be worth a look):
UnEpic - You play a D&D teenage nerd that gets sucked into a D&D-esque gameworld. Adds light RPG elements, but it's not a faultless game. Oh, and a couple of the bosses are cheesefests that up-end most of the game's flow.
Owlboy - The controls could be better.
A Hat in Time - This one's a 3D platformer, but otherwise it ticks off all the boxes.
Iconoclasts - Kodex Konsensus seems to be that this one is average.
The Mummy: Demastered - I'm serious here, it's not a bad Metroidvania, though it's way too easy IMO.
I just finished A hat in time, it was "nice". Again, could have used more upgrades, the different hats were fine, I just wanted more acrobatic upgrades or convenience upgrades, also the hat switching was a bit finiky once you got more than 3 hats. I would have also liked it if the MC in the beginning had less abilities and had to unlock them as the game progressed, e.g. no wall climbing in the beginning and you had to unlock it, though this might have made the movement less nice. Regardless, I'm gonna put this on my "nice games" list.
I played UnEpic a while ago, the controls seemed stiff and from what I could tell, there weren't going to be any of the upgrades that allow for more "ease of movement", or much of anything other than stat upgrades.
I'm not sure about the other ones, could you give me more info on the others? Like how many upgrades they have, what types, how stiff/nice the movement is etc...?
I'll try.
On
Owlboy I literally have nothing more than what I posted. I only got a chance to try it for a brief time, and the issue with the controls was something I noticed almost instantly.
Iconoclasts I played for a few hours, and the movement controls weren't an issue. Upgrades seemed to follow a logical pattern (second weapon allowed you to blast away some terrain obstacles) but what mostly bothered me about it were the boss battles. They felt needlessly convoluted and pattern-dependant. There are other Codexers that can tell you more about this one.
UnEpic's problem is that its focus... isn't focused. I can't recall with certainty a single unlock or upgrade in the game that eased movement, but there were still things that allowed progress past certain obstacles. Some of the weapons had a thing in this, like the Spear, which allowed for stabs at a considerable range, which proved to be important for at least a part of the game. No, the problem with UnEpic were the boss battles. You have the fight the seven bosses (plus an eight endurance-esque encounter that can count as a boss battle) in the One Exact Order, there's no deviation allowed from that. The first three bosses are alright as they allow for variations in approach and tactics, but the fourth one can only be done in One Exact Order, and if you've built your character in any other way than that, you're screwed. This is why there are Re-statting Stations throughout the game world, so you can rebuild your character to suit the occasion. But while the fourth boss can only be defeated via melee attacks (Big Hint there) the seventh boss can only be defeated by ranged attacks (Even Bigger Hint). So no matter how you look at it, you HAVE to completely respec your character at least once in the game... for one purpose only, for only a brief time. This is stupid. It's like playing a Mega Man game and there's only one path, one order in which to play through the Robot Masters.
The Mummy: Demastered is probably the one I can give the most info on, as I played it all the way to the end, and got the Best Ending (without really trying). You start out as a simple grunt, but you're quickly pointed to locations in-game that can yield upgrades. Movement is stiff early on, but it quickly sets a good pace. Still, you will spend some time early on scrutinizing the map to find those few spots where you can progress, always keeping an eye out for upgrades that can help you reach unreachable places later on. Each upgrade is vital, like the one that allows you to grip-walk along the ceiling, the one that allows you to breathe underwater, explosive weapons to blast away barriers, etc. It feels natural, but you also feel like you're being led through a minefield. As I said, the game felt too easy overall.
Aquaria is a little heavy-handed in freedom of movement. Areas need to be completed in a specific order, freshly-acquired abilities play too large a role immediately upon being gained. But the world just feels so... fresh that it doesn't really bother you. You'll notice when you reach the 'so dark you can't see shit'-part of the ocean and start to wonder where you're gonna get the light upgrade for that, and just go about exploring casually. The game rarely pressures you into doing anything.
Cave Story + is the game with the biggest "pitfall" I'd say. It's a game that's devious in sneaking important choices into the game without you noticing it. Something as basic as sympathetic characters asking if you'd be willing to trade your unfinished gun for an upgrade can mean the difference between whether you catch the True Ending or not. Cave Story's strongest point, however, is its awesome characters. You'll feel for them. Even some of the antagonists.
Hope this helps.