How can you say the story ? It's always the same : Ganon is coming back, Ganon is returning, Ganon, stole the Triforce, Ganon tries to abduct the world... There is never a big twist in the scenario, each character is exactly who you think they are since the beginning. Nah, Story in a Zelda is clearly not a good point.
For me, exploration and puzzle is really intricated. If it's a real open world like in W-RPG, then it's not a Zelda : there must be a little "metroidvania" effect with unlockable objects which unlock new paths, etc. So that's why I think "puzzle" are in front line side by side with exploration. When exploring dungeon, the level design is very important. I loved the first Zelda with the dungeon's name being reflected on the map, it allows the player to suppose secret room, where walls could be exploded, etc.
I don't find the battle system of Zelda very interesting (it's not bad, but it's clearly not the better point of the serie). The last Zelda games with the combo possibility is interesting, but meh. Already viewed elsewhere.
Of course, this post is clearly a personal opinion, I don't say I'm right or anything