I think the graphics should be approximately the same as it already is in the first Z. Only the graphics resoloution should be incerased, and perhaps the detail level of units, tanks and gimmicks like trees or cliffs, but it would be great if the game won't have a 3D engine but still the good old concise graphics with only a few improvements (and the owners of PC's with, perhaps, ATI Rage or Nvidia RIVA graphics card with 8 MB wouldn't say no to that idea ).
Also there could be more bridges (where you can't only send units on it but under it) and perhaps new factories. (And, of course, like you said, the old levels and videos). The main menu and the ingame-menu could also be improved (and get much smaller so that you can see more of the game screen).
Also it would be absolutely neccessary that the game supports multiplayer (with cpu and real players) on internet or LAN. It's already great fun to play together over the good old serial DirectLink Cable, but it would be much greater to game with more than one enemy and to have allies or sth.
And it would be amazing if the game music wasthe same as the old Z music, played as MP3 and having the sound of the really best MIDI synthesizer i ever heard of: Creative AWE64 Gold (although it has a little hissing and bad sound quality i LOVE it!!) It wouldn't be Z anymore without that sound.
Post your comments, ideas and suggestions about a new Z sequel here.