Cecilia and
Leonardo strike me as more romantic sounding than
Cordelia and
Theodore. I really like
Cordelia, and I enjoy
Theodore (especially NN
Theo), but between the two pairs, I'd take
Cecilia and
Leonardo. I love
Cecilia; it's so feminine and soft, and
Celia is a great NN.
Leonardo has the NN
Leo which I also adore, and while I like
Theodore in and of itself, the meaning just sticks in my mind and kind of ruins it for me. I don't have hangups about a
Leonardo, and
Da Vinci is a wonderful namesake.
I agree with Bear that Italian names seem to fit with them.
Antonia (grin),
Octavia,
Lucia,
Allegra,
Adriano,
Agostina,
Benedetto,
Bettina, etc.