I would go for a game whose story can change depending on the acts of the player. Because that kind of story could never be told by another medium, it's a strong argument for the "videogames as art" debate.
When I say the story can change depending on the player's actions, I'm not talking just about multiple endings, I'm talking about multiple endings that change the story retroactively. So, depending on the end you get, you will have played a whole diferent story everytime.
For me, the champion in this area is still Shadow of Memories (or Shadow of Destiny). It's a little forgotten nowadays, and many people don't even consider it a game in the real sense, but the way each ending tells a completely different story -- like each story happened in a diferent reality -- is refreshing to say the least.
But if you want a more popular choice, Silent Hill 2 fits the bill quite nicely. Not surprising, since it was made by the same people. The actions you have to take to reach each ending are very subtle and very appropriate to each of them, and you really play a different story everytime you go for a different ending. It's just one more reason why that game is so fantastic.
And of course, no "games as art" argument would be complete withou Shaodw of the Colossus. Everyone has already sang the praises to that game far better than I could, so just listen to them.
But in general, I don't think it's a good idea to pick only one game. Mention three or four in that paragraph, you will be a lot more fair than if you mentioned only one.