You could use Cliona- who, in some Irish myths, is the goddess of love and beauty. Other spellings include Cliodhna, Clidna, Clionadh, Cliodna or Cleena. I think it's lovely.
I just read that the mother of Angelica Kauffman (18c. painter) was named Cleophea; I've also seen Cléophée (=the French equivalent?).
There's also Cleome (a flower), Cleodora (a Greek nymph, mother of Parnassus), Cleodolinda, Cleolinda, Cleïs (name of Sappho's daughter), Clélie (Latin: Cloelia; could also be "Clell")...
Cléophée is an option.
I love Cleo/Clio a lot better as full names. ^_^ I also love Cleopatra (and know one) and wish it would come back, but I understand it's not everyone's cup of tea.
Cleodal (a glorious woman)
Cleodora (gift of god)
Cleofe (clee-oh-fee -- she who shows signs of glory)
Cleone (clee-oh-nee -- famous/father's glory)
That's all I got >.<
Thanks for all the ideas! I'm still trying to convince my DH to take Cleo just as it is, but its good to have some other options to present him with. Recently he said he might like Cleo better if we spelled it with a K, so Kleo. I for some reason just don't like that as much, I sometimes think he just wants to have had some hand in the name picking, if that makes sense.