Although I absolutely love Zelda 2, I certainly agree there are some annoying things about the game. The fact that you have to hear Ganon laugh his a*s off and then go back to the North Castle and lose all of your exp. points is probably the most annoying. By the way, if you think that's bad, be glad you're not playing the Japanese version, where if you get a Game Over, are of your levels revert back to 1-1-1! But as far as going back to the beginning when you get a GO, although it admittedly sucks, this obviously was only the second game of the series, so the precedence had not yet been set.
The next most annoying thing to me falling into a pit/lava and dying. So cheap. Nothing like ruining a no death play-through like getting knocked into lava by a horse/medusa head in the Hidden (6th) Palace...
Also, it's frustrating that you pretty much have to take some time between Palaces to grind, unless you're a Zelda 2 god. However, if you think about it, in the newer Zelda games, you almost always have a fair amount to accomplish between each dungeon, so although one can argue that Zelda 2's required grinding is tedious, it's not too much different from the rest of the series in that respect.
However, the standard combat is what makes this game so addicting for me. I'm curious to hear what other people consider to be the most difficult enemies. I used to consider the Blue Ironknuckle and Red Diara to be the toughest, but while they are difficult, they do follow pattern, for the most part. YT gamer PinkKittyRose has a no-hit play-through of Zelda 2, which is pretty freaking amazing. Highly recommended.
Additionally, I've never really understood the comparison to Castlevania 2: Simon's Quest. I played the crap out of both AoL and Castlevania 2 as a kid, and never even considered them similar. Zelda 2 has very tight (yet challenging) combat and control. Castlevania, although it has great level design, its control (at least prior to Super Castlevania IV) was very stiff. Also, while I'll agree some of the enemies have similar designs, I feel that besides that the graphic style is totally different. Castlevania (especially 1 and 3) had great use of complementary colors, while I feel that Zelda 2 had better resolution, if not quite as nice use of colors.