I didn't care for The Legend of Zelda II: The Adventure of Link when I first played it at a very young age, mainly because I was too turned off by its numerous drastic departures from the original game's now classic formula. (And yet, at the time, I had no problems whatsoever with what-we-North-Americans-thought-at-the-time was Super Mario Bros 2!)
Much later, I revisited Zelda II and gave it the proper chance that it honestly deserves--and found that I absolutely love it! I now consider it be a true NES classic on par with the original Legend of Zelda!
I salute how it attempted to incorporate more traditional RPG staples like magic spells, proper towns populated by NPCs, and experience points-and-levels into the Zelda experience! (Turn based combat and parties of characters would have been bridges too far though. At that point, one may as well play Dragon Warrior or Final Fantasy instead!)
The shift to side-scrolling dungeon crawling added a platforming aspect missing from the original Legend of Zelda game, but given the choice I do prefer the original's top-down dungeon crawling perspective. Thankfully, we've had the best of both worlds with a three-dimensional perspective from the N64's Ocarina of Time onward!
As for Zelda II's difficulty: it was indeed, unquestionably "Nintendo hard"-- especially with respect to the Thunderbird! Now that was a brutal final boss worthy of capping off a game! In general though, I put Zelda II in the challenging-but-not-impossibly-so category: the keys to success are combination of investing the time needed to level up and meet these challenges and practising your technique in mastering Link's skills! When you finally do trash the Thunderbird and master the game, it will be all the more rewarding because it was so challenging!