A linear, traditional narrative is almost always stronger than something the player has influence over. The author can build their story around a rigid arc, literary devices such as foreshadowing can be employed, elements and mysteries can be introduced that are guaranteed to be relevant or be illuminated later, et cetera. The more influence you afford the player, the worse your story is going to be, in and of itself.
However, we're talking about video games here. The strength of video games is that they're not fictional narratives. If ten million people play your game, your game doesn't have a story: it has ten million works of non-fiction that belong to your players. I think that we as video game designers should be less focused on what sort of story we want to tell and rather, what sort of environments and scenarios do we want to create in which our players can proactively write their own biographies?
Most of the impactful memories I have from playing video games aren't of cutscenes or text. I remember running a restaurant in Runescape, building a settlement with my friends in Minecraft, exploring the world in The Legend of Zelda, having Boomhauer throw dank hibachi parties at the house I built in The Sims, and so on and so forth.
But none of my examples are of decisions that greatly impact main story. I struggle to think of examples of that (granted, I haven't played a ton of video games). Like, when you blow up Megaton in Fallout 3, the main storyline continues as normal and the only changes within that context that I remember were occasional lines of dialog that told me I did a bad thing. It's just the norm for games to have stories that feel detached from everything you do in the game, and it's understandable, because it's a lot of work to make them truly dynamic.
There are also issues with the way a lot of games handle multiple endings. More often than not, you have one "true" ending and some other endings that you're not supposed to end up with. If I ask you what the ending to Cave Story is, you're not going to tell me that it's Quote flying away on a dragon. I think optimally you should have satisfying endings that are truly reflections of the player.
Also, are video games even a good outlet for a writer to tell a story? We've all played games with good stories, but would they not have been better as movies or television? One of my favorite games is Mother 3, because of the story, but I can't help but think that I might have enjoyed said story better if it were told in a proper linear medium. Is it possible for a linear story to be better because of the gameplay that surrounds it? I think these are important questions to ask.
Yuyu used a shallow karma system in Fable as an example of a game that gives the player authorship over the events that play out, but I don't think that's indicative of influence not being as immersive as linear fiction, but rather a failing on part of the designers. We still have a lot to discover in how to create responsive narratives. Video games are relatively new and we, today's video game designers, have the privilege of being the explorers and the architects of the medium's future. Of course, it's more difficult and more risky than sticking to the eon-old art of linear storytelling, but it's certainly more exciting and meaningful.
Something else worth considering also that's sort of related is that games can take advantage of certain feelings that other mediums either can't do or can't do nearly as well: guilt/remorse, pride, camaraderie. The first one is totally unique to games, I think. I don't recall ever feeling guilty or remorseful for something a character in film, television or literature has done. When a character I feel connected to does something I strongly disagree with, my connection with that character is usually broken and I start judging them more as a viewer than from their point of view. But if I harm a character in a game or burn down my friend's house in Minecraft, I can definitely feel those emotions.