Fascinating idea, indeed. I don't know about the number of cities you had in mind when you posted the thread, but my first intuition would be to start with only a handful of them until they can be fleshed out and individualized in later releases, with each city (randomly selected out of a local pool in the beginning) representing a larger cultural bloc.
Keeping in mind that the Conservatives are on the ascendant at game start, regions could be the West Coast (overall Liberal), the East Coast (overall Moderate), the Midwest (overall Conservative) and the South (overall Arch-Conservative), plus Washington D.C. as an additional 'region' with unique properties, as mentioned in the first post of the thread (seducing/blackmailing/kidnapping/murdering congressmen/senators/supreme justices, hell yeah! Since a dead congressman is just going to be replaced by a living one from the same party, this shouldn't be too unbalancing).
As each region sends its share of representatives to Washington, you can't win the game by staying in one place. Once activated, the CCS will be very entrenched in the South (more so than the LCS in the West), making inroads there should be very dangerous and taxing (as the CCS already has a formidable collaborator/sleeper network in that region that will often give away the location of your hideouts) and definitely one of the major late game tasks. The various regions should also have different 'base' opinion values, with the South being much more resilient to successful Liberal actions and much easier swayed by Conservative ones (so when you raise an issue up to 100%, you're still fighting an uphill battle against the CCS to keep it that way, unless you subvert them completely), and the West being somewhat on the other side of the scale (not quite a polar opposite, though). In addition, the game should start on the West Coast, since this might serve as a good 'tutorial level' where new players can mess around with more room for error, while the veterans will likely use the mild conditions there as a springboard for quickly building up the operational capabilities of their organization and moving on to the more dangerous regions.
With the possibility of air travel already having been suggested, an airport location in every city is a logical consequence, as are several new NPC types (pilot, steward/stewardess, customs officer, air marshal, etc.). Bringing weapons with you on a commercial flight is probably a very bad idea unless privacy laws are Elite Liberal (no luggage or personal scans). You can bring other stuff along if you must, but it's costly and probably easier to send by car a few days in advance if you have a vehicle to spare. You can also obtain a small passenger plane for private travel if you have someone in your group with the piloting skill. Unlike driving, you can't just train someone with zero piloting skill simply by flying around. That'll always end in a crash, so get someone competent behind the controls. I'm not sure if it should be possible to steal aircraft, because there are a lot less of them than there are cars and they are a lot more visible. You may have to buy one, but then, I don't really know a lot about the history of aircraft theft!
Hehe... when going to Washington D.C., you should have the option of sneaking into the Capitol and holding a speech in front of the representatives. Persuasion requirements for being allowed to actually finish your speech without being swarmed by agents and security should be very high (it's a late game thing, anyway), and you'd have to sneak in and run out through a high-security zone that's been set up around the building (so you effectively have to survive three areas in a row instead of one, although you wouldn't have to fight on your way in, so make that two).
As a difficulty setting of sorts, there could be a switch in the start menu that can be set from 'Normal' to 'Dystopia' for people who are looking for a challenge. The game starts about 10 years later with the CCS already active and all regions already turned Arch-Conservative, save for the West Coast, which is 'merely' Conservative.