For any game that attempts to tell a story, I would think that character interaction would have to be a big part. Generally, great stories have a lot in common. They are original, explore the human spirit, and let us look at life through a different pair of eyes. Of course, this can vary by how you define a great story.
So, how can you explore the human spirit without involving people? Answer: You can't. I just find it sad that most (in fact, almost all) computer games make no effort at telling a story. Granted, gameplay by itself can be a lot of fun, but it just isn't that involving. But if you don't tell a good story that involves people and makes them care about the other lives involved in the story, the results of the game are inconsequential.