I was going to say Bioshock, but then I realized it simply wouldn't work - what makes its plot so distinctive and good is that it's a slow builder. By following the story, but especially by collecting and listening to the diaries will tell you the whole story. If you want proof of that, just play it to win - no investigation of sceneries, no paying attention to details. The story won't be a fraction of what it is if you take your time. The thing with Bioshock that it does so well is telling the story through the environment, and these are things you miss if you're just playing the game like most games play. If it were to be made into a movie, that very characteristic will be gone.
Assassins Creed (the first) seems like it would work perfectly though - not only for its historical aspect and good story, but also because it works just like it could be scripted into one - get the cutscenes and important gameplay parts, and it's done.