If there is one thing I remember in particular about any Zelda game, it has to be the characters. They make the game what it is. I thought Anju and Kafei really made Majora's Mask feel a lot more emotional and meaningful.
I think its a combination of both, really. On one hand, Zelda is known for its top of the line gameplay and structure. On the other hand, we have come to love the characters. At this point, they are pretty much inseparable. When you see the Zelda characters, its almost a given that the game is going to be fantastic.
I must agree with that, though. Zelda does indeed have very unique gameplay, not just in the way it's played, but in the combination of weapons, and the assortment of ways the player can go about killing an enemy or whatnot.
However, if Zelda didn't have such unique characters, and consequently dialogue, then I doubt I would of ever taken it up like I have. Sure, if a game has less-than-decent gameplay, then it can be less enjoyable. But if a game with so-so gameplay have great characters, then I would likely still play, and probably like the game.
I also think that there is a certain point where you can't really define between the abstraction of character and gameplay tie-ins. A game can be good, but then the characters make it better, but then if the characters had been in another game, they wouldn't have made that game better.
So, I think it goes both ways, that they have to "go with each other".