Sorry for the lateness, I'm behind on my episodes--I enjoyed the discussion! Some ideas/remarks:
-- Territory-based intelligence: One thing I don't think I've seen attempted is the idea of intelligence/espionage based on territory. Kind of the idea that cities would be hubs of espionage, and that a player could direct resources toward that city. The city would then ooze intelligence/espionage capability out over the countryside--in fact a SimCity-esque "heatmap" could show how a player's intelligence/espionage capability is spreading out. Beyond the Sword did this a little, but there's room for more exploration.
This applies in the player's own territory too, and should probably stay in effect if a city is captured. If a player owns Paris and it's taken over, the player would still have great intel on what the city is producing & where the nearby enemy units are, and espionage actions should be easier to perform at first.
-- Embassies/consulates: How about being able to build a consulate/embassy in an opponent's city? That's part of how it works in real life in peacetime: a country sends their own people over and they interact with the local population, building bridges, forging ties...and recruiting assets. Often embassies are invisible in games...they could be buildable structures. Of course come wartime they get kicked out, but that territorial influence/intel would remain for a while, as sympathetic assets continue to perform.
-- Confidence levels: In real life, I suspect spy folks gauge their intel/likelihoods based on a "confidence level", as in "this informant usually gets it right, I've got high confidence in his info" or "we don't have anyone on the ground in the area, I've got low confidence that we can pull off this action". I'd be more inclined to spend those espionage resources if I knew ahead of time that an action was likely/unlikely to succeed. Even just low/med/high would worthwhile.
-- Civics matter: If an opponent has vastly different government/civics than the player, it should be harder to perform espionage. This is the "you aren't like us" factor, where it's hard to recruit assets if the opponent's beliefs are drastically different. Having 4/5 civics identical for 10 turns straight should make for easier espionage than 0/5. Taking into account the territory nationality (i.e. 10% Aztec) would make sense, as would the happiness of the population. A city having "We Love the King" parties should be a bear to infiltrate.
-- Notion of "something here": A couple of games, like Combat Mission and Silent Storm, have that way of reporting intel where your units know there are unit(s) in a location, but don't know the details yet. In most games, a player can either see a unit or they can't...it would be interesting for a player to get reports through the fog of war on "big mass of units" from their intel sources.
BTW, one board game that deals with espionage, if simply as a theme: CIA vs. KGB. It's all about deducing what your opponent will do next, and countering it.
Thanks for reading!