The spy's skin-tight outfit is actually a wetsuit!
Anyone else use spies in naval warfare? I have never played MP (and have an old version of CivII), but against the AI they can be very effective. Presumably a person would be smart enough to stack and thus avoid use of spies.
(disclaimer- many will read this and think "D'uh"; however, there are a lot of new Civ players that I think will enjoy it)
1) If an enemy ship parks next to your coast you can sabotage it to then hit with a plane or your own ship. You can also bribe it and use it against other enemy ships.
2) Pack a bunch in a transport and send off with your armada. If the other guy has a vet battleship use two spies and get it down to the red zone. Of course, you can also use bribes.
Spies rarely get captured beforehand, and even of they do after it can be worth it to sink a battleship (given the relative shield values).
I also use them to troll other Civ's coast lines (in a transport) collecting valuable "None" units, esp. engineers. However, their single best use is to scout for coastal fortresses before bombardment and for fighters in cities before sending carrier-based bombers.