It's a hard decision. Personally, if I had to choose one, it would be Minecraft. But honestly, that's really because I never really did play much Zelda at all myself, or any long game, for that matter.
But anyways, even though it doesn't really have that much in it, Minecraft has a lot of different possiblities for what you can build with with just blocks and other shapes. Beta 1.7.3 is especially good imo, despite the limitations and all that, since that was when, as I've heard a lot of people say, Survival mode was at its best, and I personally agree in those terms.
Zelda, however, I do agree about the good story and vibrant gameplay, and in fact the series is one of the few I know that is still exclusively action-adventure, and that's big because a lot of games like that are RPGs instead.