Some say that SOS stands for "Save our Souls" - which it doesn't. The Morse phrase ... --- ... was chosen as it was very distinctive and unlikely to be misread. It doesn't stand for anything.
So what about CQ? I've heard it described as "Come Quick" but that doesn't make sense.
But a chance conversation with someone while working in the US has cleared this up. He is multi-lingual (unlike me) and although he is not a radio ham, knew immediately what it could stand for.
CQ is Cherche Quelqu'un - literally the French for “looking for someone”
This makes sense as a lot of radio terms have French origins - the Coastguard still says "securite" for important information.
So there you have it - the origins of CQ. Or is it?
Pol G3HAL sent me an update. According to Wikipedia:
Land telegraphs had traditionally used "CQ" ("sécu," from the French word sécurité) to identify alert or precautionary messages of interest to all stations along a telegraph line, and CQ had also been adopted as a "general call" for maritime radio use. However, in landline usage there was no general emergency signal, so the Marconi company added a "D" ("distress") to CQ in order to create its distress call. Thus, "CQD" is understood by wireless operators to mean, "All stations: distress." Contrary to popular belief, CQD does not stand for "Come Quick, Danger", "Come Quickly: Distress", or "Come Quick — Drowning!"; these are backronyms.
This sounds more likely.