One thing I'd like to see in a Paradox Cold War game is the possibility of a start date before 1945.
Yes, I know there was no "Cold War" before 1945, and a start date that includes World War II would seem to tread on HoI's territory. The default start for the base game should be 1945 (or 1950), just as 1066 is the default start of CKII. But like CKII has had a couple of DLCs that make it possible to start earlier, I'd like our hypothetical Cold War game to have the option, even if only in a DLC, to start as far back as 1922. In addition to being the year Stalin took charge of the Soviet Union, it is also the year that Mussolini became prime minister of Italy. Because I envision the Cold War game as being as much about the spreading of ideology as it would be about preparing for (and trying to avoid) nuclear armaggeddon, and pushing the starting date to before World War II has been fought would make Fascism a potentially viable alternative to the binary USA/USSR setup that some people in this thread have expressed concern about.
Not that V-E Day extinguished all Fascism forever, of course. But with an alternate World War II where the Axis was more successful, its most powerful proponents would have had a lot more influence in the course of history to come, and the Cold War could have ended up as a standoff between three major ideologies instead of only two. Or possibly still two, but not the same two.
Starting as far back as 1922 could also mean the Nazi Party never comes to power and the Axis as we know it never forms, but that's alternate history for you. But I think it would be fun to have the option to give other nations the chance to try to enter the Cold War as superpowers, and open the game with a race to see who will be the first to develop the nuclear weaponry that will allow the Cold War itself to kick in and drive the course of the rest of the game.
No, I don't think every playthrough should require the player to risk not having the Cold War we know from history in-game. And I certainly wouldn't want to have to work my way through World War II every time I wanted to start a new campaign of a game that's supposed to be about the Cold War! That's why I'm perfectly happy to consign this content to a secondary start date available only though a DLC. The base game, by all means, should start out as the familiar Cold War, with the two major ideologies and two initial superpowers we know from real history. Clearly that's what most people who buy a Cold War game are going to want, and I'm all for that. But if DLC can allow Crusader Kings II to begin 326 years before the First Crusade, surely it wouldn't betray the point of a Cold War game to allow, just as an option, a couple of decades of pre-Cold War setup for those who feel like reshuffling the players and deciding on a different balance of power for the era.
As for treading on HoI, I'd say the war mechanics of this game clearly wouldn't be as deep as in that series. HoI was designed from the ground up to be able to simulate with richness and depth all the minute details of leading a nation in the midst of the largest war in history. (I assume; I haven't actually played it.) Our hypothetical Cold War game would be far more focused on politics, espionage, and diplomacy, with most actual in-game wars being relatively small-scale proxy wars. It wouldn't need to be able to support the same depth of war mechanics as HoI does. So it really wouldn't compete with HoI at all, since that series would still exist for anyone who wanted to immerse themselves in the detail-oriented total war experience it offers; the World War II that would be fought in my hypothetical DLC could afford to be run at a much more superficial level than that, seeing that it's really only there to determine who the superpowers are and what ideologies they dominate with once the real meat of the game, the Cold War itself, gets going.