I find that everything being randomized would be interesting, making the random factor makes everything much more believable, and making sure that every time you got a more "realistic" play. As said above.
Also I wouldn't make one main quest that once you've finished it your done. Sure there should be a main quest to keep the player doing something and keeping attention but look at oblivion for example, or fallout 3 (with add-ons), it made it so much better that you can do all these little side missions AFTER you beat the main quest. But as Jackal touched on, a survival system. Nothing makes a end of the world make better then feeling that you have to FIGHT to survive. Food, water, etc. Take Wicked Rising for example, they are using systems that no map has EVER used before (or at least that I know of), it is a completely new type of survival system. Take some ideas from them (I don't mean copy their whole map and set up but you know, just look at their systems and perks, etc.). Still be creative though and make up most of it by yourself. If you want help if a story line go talk to Newbchu in his story line "workshop" in the top of this forum. Good luck though! You've got a lot of competition for survival/zombie maps.