I'm in the "I really enjoyed Zelda II" camp, though I believe that it is far from the best Zelda game.
I've always used a guide whenever I've played through the game, and therefore I've never found it to be all that difficult. If you play it without using a walkthrough, it's easy to take a wrong turn and end up in an area where enemies will destroy you with ease because your level is too low.
I enjoy the combat, and the overworld has a very unique and interesting layout. The music is also pretty memorable, even though it has a weird vibrato sound.