I don't think I would allow units to share squares, makes things too complex. What if 2 different civs have hidden units on a square, and a third unit moves in, at war with the first civ, not with the 2nd? This kind of thing would put the onus on the game coders, lots of work figuring out how to allow for all the situations that arise.
That said, I do like the idea of hidden and hidden nationality units. There are a lot of issues to be worked out, for example, how to keep the AI from building tons and sending them at you, when ostensibly the civ leader likes you? Need to be some rules about when HN harrassment can occur, i.e., civ must be furious at you, or you must have just attempted a failed spy mission, or committed ROP rape on another civ, etc. The player must also be limited in building these somehow, maybe a good way would be to link the number allowed to number of cities, as with Armies. You could have only 1 Spy or 1 HN guerilla for every 10-15 cities. They should cost several gold per turn in maintenance also.
Have to code the AI not to automatically know where the hidden spies are, and figure out a way to let it do periodic searches, NOT based on gold.
I would like to see spy units back in Civ4, with less function than the civ2 units. Disallow plant nuke, except for some governments. Propaganda attempts would make the city a barbarian city, not give it to you. The barbarian city would simply fortify all its units, daring somebody to come and take it. No more Steal Plans for worldwide disposition of enemy troops, spy must get next to a city and Steal Plans for that city and perhaps a couple more around it. Steal Technology would be done by the spy unit, only allowed in cities with libraries or the capitol. Some other things the spy could do: Start Riot - make a city riot for 2 turns. Sabotage Military - freezes all military units in a city for 2 turns, based on destruction of needed military supplies - horse fodder, gunpowder, fuel, what have you. Things like destroy improvements I would disallow for spies, best handled through war, or perhaps terrorism? Also, might be neat if spies could assassinate specialists in a city, to screw up celebrations, corruption, etc., sort of like Poison Water Supply, but with specific targets. Some of these abilities would come with discovered technologies.