I think LoZ dungeon 6 and the second quest are way, way harder than all the other Zelda's together, including AoL.
MM was more complicated to get 100%, but I think LoZ took me longer to get everything. Walking trough walls (without a lens of truth) took me a loooooong time to discover and all of my bombs, then I got frustrated and walked right through...
Then, I needed bombs again. And the heartcontainer on te beach in AoL, one of those few squares that I didn't walk on.
The first few Zelda games were quite easy to keep track of everything you could find. There weren't that many things to collect. All the items were on screen or in the manual, so you knew what you were searching for. When you found something, you got it.
MM was more tricky to find out when to do stuff. I remember clearing the ocean spider house and getting nothing... It was the wrong day, or I was the wrong character, I can't remember, but I thought that was stupid.
AoL had some cheap deaths (like almost any other game on the NES), the game itself wasn't cheap at all. I thought controlling your character worked very good in fact. I can't tink of other things that could be seen as cheap...
The music was great, the graphics were alright, even good for that time. Restarting at North Castle? At least you could save this game, unlike similar, more difficult action platform games.