Reward players as they go through the tutorial, not just when they complete it. Not just with gralats or hats either. When they start they don't need a sword, bombs or arrows. Teach them how to do things individually and then reward them with other options as they go along. Make the tutorial more linear. A player should understand how to navigate the UI before you start throwing gameplay at them. Make it more directed, not by using tacky arrows to point to the next objective like some games do, but by having the levels actually guide the player through the tutorial.