I think it should start when the main characters get left behind in the town. Start with a face paced sequence, preferably a battle before too long. Just start thinking of possibilities for your story. When it comes to openings, you want to give them a fast paced opening that is interesting, and pulls you into the story. A battle scene is particularly a good thing near the very beginning of the game. Think of how they did it in Final Fantasy 7. Avoid giving too much about the story until later. People will get that zombies == bad. Maybe you could communicate that it's transferred via bodily fluid by having one of the initial party members become infected. Use dialog in such a way that it is clear why he is transforming, but avoid "info dumping" (them having a discussion). You may want to try something like
Character A: "$@#%, some of the zombie's fluids must have entered his blood stream."
Character B: "We have to kill him. He's infected!"
Character A: "We can't just-"
Character B: "He's going to become one of them! He'll kill both of us if that happens!"
Character A: "But..."
Character B: *destroy zombifying body*
You should tweak that kind of a scene to reveal something about the characters involved. This gives us the knowledge that the infection turns people into zombies, and is transferred via bodily fluid. Scenes like this are more effective at setting up the world than exposition. Once the story gets going, and the audience is interesting, we can get more detail. The flashbacks should wait until we get a solid grounding in the game's "present".
Also, I think it would be kinda cool if one of the main characters was infected, but somehow managed to counter it before he became a full zombie. That way he'd have some zombie like abilities, but maintain his sentience and humanity. This would also make him a perfect zombie slayer, since he couldn't be further effected by the virus. Maybe at some point, you could have his cure/counter start to weaken, and the zombie side of him begins to get stronger.
Just tossing out ideas that came to me, I like brainstorming worldbuilding possibilities. I think you should keep the virus transferred via bodily fluids, as it would feel even MORE like I Am Legend if you didn't. Also, it would make for an interesting scinario if you have one of the characters get partially infected. Especially if there is a romance subplot going on involving that character ^_~