Interactive stories are a something I find interesting. I apologize for what follows.
Dear Esther is less of a game, and more of a story. It is interactive, but your actions have no effect on the story. The story is conveyed partially through the narrator, and has some added nuance through details in the scenery.
Heavy Rain is a interactive story, in the sense that there is a story, and your actions affect it. It's certainly the the most well known of those types of games, recently. (Though David Cage et all have a new game coming out next week). The thing is, while it's almost certainly the game with the best production quality, it's not particularly great. In Heavy Rain, you don't make meaningful choices. One could argue that you don't make choices at all.
During the game, you look for clues. Roughly, the plot of the game is that you look for clues, you find them or you fail to, and then you go look for another clue, until time runs out and the game wraps up and ends. It's not presented to you as a choice. You need to find the kid, and you need clues to do that. There's no reason you would want to purposefully miss a clue, so the only way that happens is when you screw up. The most important "choices" you make aren't choices, they're just penalties for overlooking something or screwing up a quick-time event.
In a linear story, each plot point leads to the next. e.g. P1 -> P2 -> P3, until the end of the book. In an interactive story, the plot branches, obviously. The more choices a player has, the more interactive the story appears. The problem is, we can't actually give the player infinite choices, since obviously it's impossible to write code to deal with every possible choice a player may make. We don't have anything that can handle the interactions necessary to make the game a sandbox and let the player run wild. Instead, you end up with things like Mass Effect, where the game tracks things like your reputation, previous dialog choices with NPCs, etc. They try to make NPCs react to you in an interactive and organic way, but your interactions are still governed by the limitations of the game.
Convergence is a trick used to give the illusion of choice. Rather than write several different plots, for each choice you make, the authors will write a few lines of dialog seperately for the choice you made, and then throw you back into the same plot line as everyone else. If, say, you choose to kill the sympathetic antagonist mini-boss, you get a line about how he had it coming, and if you spare his life, you get some line about how merciful and compassionate you are. And then the plot progresses. The longer the game lets you believe the plot is solely about the outcome of your choice, the plot feels interactive. Often you can see this in plot missions:
I'm sure you're also familiar with stories with multiple endings. Choose your own adventure books have them, the movie Clue has them, binary morality system games like Infamous have them. They change the narrative of the fiction, but they don't always do a great job at making it interactive. For example, right at the end of the game, Bastion had a choice. It changed the outcome of the story, sure, but it was a little lazy: nothing you did up to that point affected the outcome. No one would call it an interactive story game. Similarly, Infamous gives you an ending based on your morality. If you were evil, you get the evil ending. It feels better, because it's tied to your actions in the game, but it's also not really very interactive: the plot is the same all the way up until that point.
Heavy Rain basically just has multiple endings. All that happens when you fail to find a clue is that the scene ends early and moves you on to the next one. Occasionally, you might skip a future scene or get an extra scene depending on your outcome. It's really an extraordinarily linear game with a few multiple endings (mostly decided on a few quick-time events in the last twenty minutes.)
If you really like interactive stories, you should look to text adventures (often called interactive fiction). [IFComp](www.ifcomp.org) is a good place to start, as is Brass Lantern, and aeontech recommended Emily Short's blog here about a year ago. One of the major reasons modern games don't have many choices is because of the high cost of adding a choice. Writing it, scripting a new cutscene, recording voices all costs money. Interactive fiction have some of the most complex choices, because they don't have to deal with that; the cost to add new choices and new scenes is minimized.
If you're interested in some theory about interactive stories, I'd highly encourage you to read the book Chris Crawford on Interactive Storytelling. I read it sometime when I was in elementary school, for fun, and it's remained one of the more interesting books I've ever read. Here's a review of it.
By the way, no "interactive story game" will ever be as interactive a story as can be told with actual human interaction, such as Dungeons and Dragons or free form role-playing and storytelling.
Façade might come close though, it's probably the closest thing I've seen to organic, unlimited choices, while still being something resembling a game.