Zelda II: The Adventures of Link. Not only is it the hardest Zelda game, it is usually in the top lists of hardest games ever (at least, if the list is made by a competent gamer).
The Legend of Zelda (first game) was a piece of cake, and I could beat that no problem over and over again. The Adventures of Link had insanely tough palaces, impossible bosses, and you even had to dodge those flying head things while jumping pits of lava, which would usually end in your death.
Not only that, you had to manage to get to the end before a game ending glitch sent you back to the beginning (at least if you had a launch copy like me)