Between the two NES games, AoL is definitely my favorite. In the original, you didn't exactly have "puzzles" as much as you had trial-and-error pushing blocks and bombing walls to get through dungeons. In AoL, you have to figure out which spells to use in which situations. Not as complex as some of the more modern games, sure, but it still had you thinking about it a bit more. AoL does still have some trial-and-error elements, though, like having to find the cabin hidden in the swamp. I'm not really a fan of that, but at least it's spread out a bit more thinly than in the first game.
Difficulty's kind of a gray area. It can be a bit tricky, sure, but once you learn the enemies' tricks, you can usually defeat or avoid them fairly easily. Someone earlier mentioned the enemies on the fence that throw stones at you. They throw the stones so that they'll hit you if you keep moving at your current speed. Just take your time and move back and forth a little bit and they won't hit you much, if at all. Plus if you take the time to level Link up, the game gets even easier.
Someone also mentioned clues that you might pick up from one town that you'd have to use in another, but they're so far apart that you might forget by the time you get there. I remember when these games were new and they came with instruction booklets. There was a page in the booklet marked "memo" that was specifically meant for you to write that stuff down. Obviously we might not have the luxury of getting the game with the booklet, but I'm pretty sure everybody has access to a pencil and paper somewhere. If not, the 3DS has a built in Game Notes app, and anyone with access to a computer can type it up in Notepad or draw something in MS Paint (or whatever the Mac/Linux/whatever OS equivalents are). In all honesty, I'd prefer that over having a companion character constantly telling me where I need to go, but I guess that's just the kind of gamer I am.
So yeah, I like the challenge, I like the deviation from the standard Zelda formula, and despite being on the NES, I think it's a worthy member of the Zelda series.