I always thought that changing how the way spies work could add much more to play strategy, as well as to realism.
I have some proposals, few of them are inter-compatible, and some are harder to implement.
Anyway:
1. Disguised/chamaleon spies
By default, spies could be seen as spies only by the owner (or by allies or with shared vision). Otherwise they looks like a different unit, e.g. one explorer. Another option is that they are camaleontic and, depending on the ownership of the terrain they are on, they could be seen as Workers (own terrain), Settlers (unclaimed terrain) or explorers (enemy terrain). Veteran status is disguised also. When a enemy tries to attack or bribe disguised spies, there could be 2 different behaviour: (a) the attack/bribing option is canceled (unit keeps intact mps) and spy is flagged "known" and message "spy has been discovered!" is sent to board; (b) the attack/bribe goes along but a message is sent to board. If Spy is on a stack with other units, it is not attacked, but a message is sent, discovering the spy. In a city, the spy keeps disguised unless it is attacked.
2. Unidentified spy
Spies could always been unidentifiable: their nationality is secret unless it is allies or shared vision. Their colour would be grey, and a flag with a "?" associated with them.
3. Add "hire double agent". Spies could "infiltrate" other spies or even other military/civilian units. Instead of bribing they should "hire" the unit. The only effect is that the "double agent / infiltrate unit" will show its vision, and all related action reports (such as battles etc.) will be reported in message window. To infiltrate/hire, the spy should pay lot of $ and its success chance should be very low. There should be a way to uncover enemy double agents, e.g. just by having that unit in the same tile of a loyal spy. A message should be sent also. If a infiltrated unit enter a city, it gives vision to that city.
4. Same as above, but spy is unseen and "carried" by the infiltrate unit, and can leave it when she wants. This could be apllied to cities also: spy "enter" the city and stays there, giving vision of the city.
5. Spies are always unseen until a enemy unit accidentally walk or attack its tile.