Ooops I just typed out a response and my internet cut out and it didn't post.
I love
Constance-- It was my great-grandmother's name. Her combo was
Constance Margaret. Some other
Constance combos I like are:
Constance Jessica,
Constance Alberta,
Constance Dove and
Constance Diana.
I would not worry about it seeming "Old-lady", I do not believe that datedness should affect the quality of a name (and
Constance is a good one!).
If you don't like
Connie, may I suggest
Nancy or
Tansy as NNs?