I think there's really only three things that we can agree on when it comes to meaningful character choices within videogames.
* We want more of them.
* Knights of the Old Republic got it right.
* Fable got it wrong.
I'm playing Knights of the Old Republic right now, and one of the things that strikes me is that there's really one only choice - do you embrace the light side of the force, or the dark side? All of the lesser choices in the game are really only aspects of that larger choice.
That's of course been done elsewhere, and done poorly. Often when games give players the choice between being "good" and "evil", it's ultimately a fairly shallow choice, where the end result is that you're exposed to one of two alternate endings. Bioshock is an example of a game that handles these kind of morality choices badly.
The reason why that kind of choice is unsatisfying is to do with the nature of stories. Stories have a force and direction that is not entirely within the control of the author. They follow a pattern of covenant, terms and closure.
The first act of a story establishes a covenant with the audience; the story makes a promise about its scope and direction. The covenant lets the audience know when the story will end, and who will be instrumental in its conclusion. The first act asks a question; it is the desire to see that question answered that motivates the audience to continue their participation, and it is the answering of that question which will eventually close the story.
The second act sets out the terms of the covenant; the second act defines what is at stake in the story, both in terms of the plot and the theme. It narrows the ways in which the plot can be happily resolved, creating an illusion that there are no positive outcomes remaining while keeping a doozy of a finale up its sleeve. (In tragedy, the second act offers the hope of a miracle solution which the third act will snatch away.)
For any given first and second act, there is only one appropriate third act. There is only one ending which is the natural and powerful result of what has gone before. While you can create alternative conclusions, there will unfailingly be a "better" one.
That's why alternate endings in games are often unsatisfying; one ending will feel like the "real" ending while the others will come across as suggesting the player has failed in some way. In worst case scenarios (Bioshock) both endings can feel equally wrong.
The way that Knights of the Old Republic handles the dilemma is simple - it changes the second act. The first act tells you that this is the story of the clash between your character and the evil Darth Malak, but the second act varies depending on your actions in the early game. If you're playing a "good guy", everything in the plot starts hinting that this is going to be a tale of redemption and free will. If you're slaughtering innocents left and right then you'll find yourself embroiled in the tragic tale of your corruption and fall.
Either way, the plot feels as though it's the plot you were intended to experience. You don't feel like you're bucking the narrative, and you don't feel like the game's desperately struggling to make sense of your actions. And the conclusion, naturally, will be the inevitable result of the first and second acts.
This is what we need more of in games - not alternate endings, but alternate middles.