Beat Gargoyle's Quest II today.
It improves on the original in a lot of ways: Firebrand seems to control a little better (Not that Firebrand controlled badly in the first game), random battles were nixed, and the level design (especially in the last few levels) really pushes you to make use of the powerset you're given (The magic claw, the tornadoes, etc.)
I think my only real problem with the game is that it's not the huge step up I would have expected from the first game. It feels like the biggest improvements were on the presentation side of things, and that kinda comes with the territory, seeing as how the series jumped from Game Boy to NES. Aside from that, there's nothing in the game that couldn't have been done on Game Boy, which is probably one of the reasons they did end up porting the game for Game Boy. If I'm not mistaken, the GB port has two exclusive levels, so I'll have to track that down soon, too. Overall though, it was a pretty fun ride for the most part, though there is a stretch of the game that's particularly perilous, if only because it's a stretch of about 5 or so levels with no password in between, so dying anywhere during the first 3 of those levels will set you back quite a bit.
Probably going to bite the bullet on Demon's Crest sometime soon.