I highly recommend both of the games for the PS2 made by Team Ico. Their debut title, Ico, has a heavy focus on puzzle solving that somewhat resembles that of the Zelda series. Their second title (and my personal favorite game of all time), Shadow of the Colossus, is centered around exploration and combat. Both games are masterpieces (my opinion of course) and I think a Zelda fan would feel right at home with either title.
EDIT: S'more great series that are a little different than Zelda but are nonetheless amazing are Fire Emblem, Kingdom Hearts, Final Fantasy, and Ninja Gaiden. The last one is a bit of a reach, but I was just remembering how cool those games are while I was listing stuff.
If you are a fan of Puzzles, adventure and role playing I would recommend many of the PS2 era RPGs - Kingdom Hearts, Dark Cloud, Final Fantasy series, Shadow of The Colossus and more. I would also recommend the Elder Scrolls series, Dragon Age, Fable, Tales series and Fire Emblem.
Sure Darksiders fits the bill as Vigil Games representative Mases Hagopian is earnestly trying to convince this forum.
Other franchises which you may enjoy are God of War, Assassin's Creed, Final Fantasy, and Minecraft (I suppose not technically a franchise yet). The first two are rather gory and more action-oriented therefore I don't know if you'd like that. Final Fantasy is an RPG rather than Action-Adventure game like Zelda but if you really want some high quality story and gameplay check out installments I-X. Minecraft, well that's adventure right? Making your own worlds and goofing off. XD