Have you tried Shovel Knight yet? (I haven't, unfortunately.)
I have, actually. Graphically speaking, it feels kind of like someone used the Mutagen from TMNT on the Mega Man 6 engine, and as for gameplay, I can't think of much like it, really. The story is light-hearted and kind of silly, and the controls never feel like my screwing up wasn't my fault. It's quite well made, and pretty to boot. The whole mechanic of collecting treasure reminds me of DuckTales, but without the baked-in character motivation (Uncle Scrooge wanting to prove he's richer than GlomGold, as always). I am never exactly clear on why the Knight needs all these gems and gold and stuff...
I guess Armor is expensive? Certainly, shovels can't be. I really haven't played much of it yet, and it's been a while.
Cave Story, on the other hand, has the strange quality of coming off like it's not based on anything else. There just isn't anything I can think of to compare it to aesthetically, or gameplay-wise, other than the obvious mechanic of exploring and not being able to access areas without the equipment necessary to do so.
Correct me if I'm wrong, but didn't this used to be called an 'adventure' game? Everyone says it was necessary to give this genre of games a specific name, but I thought it already had one. Somehow 'Adventure' has transmogrified into 'MetroidVania' because people noticed when SotN ripped off Super Metroid's map system? So what? Kid Icarus did it before either of them.