I'm going to go against the grain here. I actually tend to quite strongly dislike storyline altering choices in games. I find they massively cheapen the storyline and ruin any sort of immersion.

I'm playing Tactics Ogre: LoCT and I have to say I have about zero sense of involvement or care about what is going on in the story. Knowing that it's just all relative I just can't get involved. Each branch individually is probably something I would quite enjoy if it was a self contained story on it's own.

(Choices in game-play are fantastic though)