Oh, the Metroid game available through the ambassador program was Fusion, not Zero Mission. It doesn’t really matter though, because you can’t get it outside of that program anyways.
For my money, Cave Story had a little too much fiddly execution bits, and the world didn’t really have a sense of place for me, it was just sort of confusing video game levels. It also has a sort of weird traversal mechanic, where you use your gun to sort of jet-pack around, which is where some of the fiddly execution comes in. I think it has a reputation for being very hard, but IIRC that’s basically only if you want to 100% it. It’s perfectly do-able to beat normally. But overall, it started as a Japanese PC doujin game, and it really feels like it.
As noted, the original DS Castelvanias are good. I’d probably skip the first one (Dawn of Sorrow), because that had some stupid 1st gen DS game stylus stuff in it. But the later ones (Portrait of Ruin, Order of Ecclesia) are pretty good, Ecclesia being the last and probably best one. Those games are basically direct successors to the GBA Castlevanias, which were in turn a kind of direct offshoot of Symphony of the Night. I don’t really know how the GBA ones would hold up now, but I suspect they’re fine, if outside of your 3DS requirements.
I would also recommend Steamworld Dig, which looks kind of low-rent, but is actually really very good. Also easily available on eShop.
I’ve played through the various Shantae games available, and while I finished all of them, I can’t particularly recommend them. They use the basic WayForward engine, which has pretty unsatisfying physics and feels like a super mediocre licensed platformer (which makes sense, as its been used for many of them). They’re also super linear, with some very basic lock + key mechanics for the various powers and locations. There’s no real sense of discovery or surprise anywhere.
I do think that some of the MegaMan ZX games push some metroidvania-y buttons, but they’re ultimately more MegaMan X than anything else. They’re also pretty punishingly hard.