The best story in any kind of game (board, video) is when it is emergent rather than coded into the game.
"Emergent" means that the systems, choices, and randomizations of the game create a kind of narrative as you go. In Minecraft, for example, you can probably tell a great story after 20 hours of play ("I started on this cliffside, struggled to set up a decent shelter behind the waterfall, kept getting attacked at night by a witch from some nearby swamp, then found a passage down into the caves below and some diamond for a sword, went off into the swamp to hunt that witch... etc ") and it will be different every time.
Or in an old-school tabletop RPG, emergent story is when the dice and randomization create encounters and situations that no one planned (certainly not the DM, who shouldn't be a storyteller but just an interpreter). You see results play out and you interpret those as a story. That's how it should work.
I don't even enjoy most games calling themselves "RPG" anymore since they treat choices like a pre-arranged tree--like a Choose Your Own Adventure book. If it's just a matter of going own different pre-planned trees, it's still boring as hell to me and feels totally artificial. I'd rather have a game with great systems, options, and randomization, which is rich enough that it ends up telling a story as you play. That's far more interesting than voice actors and all the other nonsense on pre-planned paths.