The big thing these days is to let your players choose. Sometimes, these choices relate to the fact that it's an open world where any issue can be approached in a thousand ways. Sometimes, these choices are scripted nodes in the plot.
Let's skip the weaknesses of scripting choice, except to say that it's not a very scalable or satisfying method of adding choice to a game.
However, adding choice to the world itself...
A lot of games have done this pretty well. Crackdown and Skate are two examples.
Usually, this is tactical choice. Approaching a situation from any direction you please, carefully allowed by permissive level design.
But this method is also flawed. The difficulty here is that if you let a player choose, he'll choose the same thing over and over again.
For example, in Crackdown I killed every single boss by kicking them in the face. Whether this was algorithmically a dominant strategy or not, I certainly felt it was. I never felt any urge to kill bosses using guns or grenades or whatever.
Skate took this problem in hand by giving you missions that specifically required different actions. This mission is about grinding, this one's about jumping through a hole, this one is about long air, this one's a race...
Therefor, Skate had the opposite problem. While I very much enjoyed the game, occasionally a mission would be snap-your-controller level frustrating. I can rack up ten thousand points in thirty seconds, no problem, but don't ask me to manual to jump to manual, that's just too hard. Let alone those races, which were just asinine.
While Skate's physics give the player freedom of choice, the actual "plot" was engineered to make you experience the full range of abilities. That's not a bad idea... except when you take it to extremes and require the player to excel in every ability in order to advance. That kind of defeats the purpose of choosing in the first place.
As another example, I have always loved the old Buck Rogers games. Ancient things programmed in a familiar engine, but better.
Back in those days, they were happy to let you build every member of your party from scratch. Unlike normal D&D, things didn't always boil down to combat: it was common to have to do zero-G maneuvers, naval combat, bomb defusing, fast talking, and so forth. So the game wasn't so much about minmaxing for combat.
But, like the worst in Skate and Crackdown combined, this game required you to both excel at everything and once you had decided on an approach you were basically stuck doing it for the rest of the game.
Scripted choices have this problem as well. How many people actually "risked falling" in KOTOR? 99% of the players either always chose good or always chose evil. Even though there was a choice, it was only a choice. One choice. Made near the beginning of the game.
Similarly, did anyone actually kill a few of the Little Sisters? I'm pretty sure that everyone either killed them all or saved them all.
In both cases, there might be a few outliers where the player changed their mind halfway through. For example, I wanted to be Sith in KOTOR... but after a few planets I found that "evil" was just another word for "spoiled thirteen-year-old boy", and didn't really have any urge to re-visit that particular phase of my life. So I became "good", which is apparently just another word for "naive thirteen-year-old girl". Which is better only in that I have never been one before.
"Choice" in games... no. Never put "choice" in games.
Put in choices.