I have never seen the appeal of Cleo, personally; it reminds of something that a pet would be named... particularly a cat or a horse. Written, Clio is a little better.Cleopatra is quite much, indeed. While we're on that name, I actually saw a stone in a cemetery for a woman by the firstname of Cleopatra (it was interesting and unusual, especially because she had been born in the 1800's.)Clementine has always seemed like it would garner assumptions of the bearer being inadequate or weak. Infantile.I will list a few possibilities (take a look at their variants, too): Clotilde / Clotilda Cleona Cloelia Cliodhna Clodagh Clover Claudine Clarisse Calanthe Calfuray Calliope Callista Celeste Constantina Candace Angelica Riccarda Leona LeonoraNicknames do not need to be a perfect match to legal given-names. Sometimes the best diminutives are for the most unlikeliest of fullnames (even if they are absolute opposites.)Good luck, - Francesca