Odesa
There were at least two cities (Eupatoria and Theodosia) with names that sound 'feminine' for a Russian; also, Catherine II did not speak Russian when she was a child, and lastly, all cities are feminine in Greek (and in Latin). Another story is that the name 'Odesa' is from word-play in French. French was then the language spoken at the Russian court. 'Plenty of water' is assez d'eau in French. If one says this backwards, it sounds like the Greek colony's name. Word-play about water makes sense. Odesa is next to a very big body of water but has a little fresh water. Anyhow, there is still a link with the name of the old Greek colony. So there may be some truth in the things people said long ago.