I haven't played Heavy Rain but I really enjoyed Farenheit / Indigo Prophecy. Your choices had a limited effect on the structure of the movie, but the game was making constant nods to what you did, often in clever ways.

Heres an example. In the very first scene you have to flee a crime scene. You could leave the murder weapon where it is, or try to hide it. If you hide it, the game doesn't show you where you hid it. Later on, you play as the cops investigating the crime scene. If you didn't hid the weapon, it's in the same spot, but if you hid it, you'll have to look for it now. Most changes to the movie follow this structure. Demonstrating a higher level of play results in a movie with more and longer scenes, and all those extra scenes make it very clear that your actions caused them to exist in the movie.