I think that the truly great Adventures have all of these things, and all are equally important in their own ways. A great story, told by memorable characters, in a rich and expansive setting. That's the core of it. Puzzles can add a lot of depth when integrated well with these elements. Combat and stats can also add an interesteing twist, but at that point we're getting into hybrid territory.
Features that add to the experience include voice acting (which can help to make even the most boring characters memorable), an appropriate score or soundtrack, and high quality art and animation. These things increase the immersion considerably.
From what I've seen in the initial Demo, Quest for Infamy is loaded with these elements.
It's also nice when all of the characters have their own motives and desires. I like when side-quests are offered, even if they are small. I love selling creature bits to the Healer / Apothecary in Quest for Glory. This kind of thing brings considerable depth to the setting.
Similarly, having multiple solutions to a puzzle or problem can be a lot of fun. It's a good way to add a bit of realism to the game.
Along those same lines, think about items and inventory. In a lot of Adventures that I've played, every item that can be picked up is useful exactly once in a specific area. It can be nice to use the same item for multiple purposes. Or it could be nice to have items that are completely useless in the game. These could be rewards or red herrings, but you never actually use the items to solve any puzzles.
Anyways, just a few thoughts.