Great post! I totally agree! Number 6 is a very interesting idea! And should technically be no problem?I really hope that this thread marks the beginning of "The Return of the Warlords". I've never played a better strategy game so let's hope this thing will come to life. Here are some loose ideas that came to my mind when I thought about why playing Warlords was so much fun.
1) Turn-Based. I think this is set but I mention it for completeness.
2) Simplicity. Have a simple gameplay where the complexity comes with the number of opponents, the number of cities and so on. It's like with chess: simple setup, simple rules but complex decisions. Forget about the tactical map, it drags you out of strategic mode where you have to juggle with lots of cities, armies and so on.
3) Beauty. I would like to see innovations in the area of displaying the world. Up to now it is quite obvious that the map is rendered using square blocks. Perhaps there could be something like fuzziness, procedural maps, whatever to add more realism to the game. That means the map doesn't look so artifical but natural.
4) Seasons. Seasons could influence the game play: lakes freeze over during winter so that armies can pass, rivers run dry in summer, fires burning forests
5) Quests. Avoid the "Quest Storm" at the beginning. Instead let the quests pop up occasionally. Have multipart quests, like with geo caching, where the hero gets hints with each location. Perhaps small riddles must be solved.
6) Cloud-based Games. I start a game on my desktop PC in my living room, then I take my tablet and continue the game there; perhaps I can even continue it on my smartphone.