I'd really advise Fahrenheit (or Indigo Prophecy, depending on location). It often really does feel like actually being in some kind of movie, and the level of interactivity for a large part of the game is very interesting. Often it feels like the actions actually have some meaning. Unfortunately it shares a failing with the movies it attempts to emulate, namely that towards the end the plot speeds up with too much emphasis on action and less on developing characters. Other than that it was money well spent.

Oh, Mafia's good too.