If we go back to traditional zombies, then we need true realism as well. More like Condemned than CoD, as well. Start us off in an organic city, randomly, and begin the virus spreading. In the early stages, obviously we will have an advantage over the NPC's because the game title will have 'Zombie' in it so during that time you try and collect weapons, ammo, friends, start up a safe place etc.
As the number of zombies increases exponentially, the game will get harder and harder with a decent learning curve. Perhaps after a certain time, when you are expected to have either a decent base and/or weapons, the army can come in to try and kill everything, Half Life style. I'm not sure, but I think something like that is the only way trad zoms will return. From the dead.