Catherine definitely is timeless and beautiful, not at all boring. It has a lot of absolutely wonderful namesakes (Catherine of Aragon, Catherine the Great and Catherine Earnshaw). Catherine Elena would sound absolutely marvellous.
I prefer Catherine over Charlotte. While I do like Charlotte, I do think that Catherine is a much more elegant name.
Catherine is a classic name and its also my name but I spell it Katherine. Personally, I like it spelled best Katharine because it's the original spelling and Catherine with a C looks so boring to me. Just a warning EVERYONE will pronounce your daughters name like Cath-ryn instead of Cath-er-ine and she will always be asked if she goes by Cat or Catie. I go by Katie because I think Katherine just doesn't match my personality. The only thing I really can't stand about my name is how incredibly popular it is! Catherine and variations of it are so popular there's always multiple Katherines, Katies, Kats and Katelyns in my grade. I've been teased a couple times too about my name being "too old ladyish" but I guess older names are coming back so your daughter probably won't have to worry about it. I like Charlotte more than Catherine but I would be worried too about Charlotte becoming too popular and you can never go wrong with Catherine since its a classic with many nicknames.
I love Catherine! I would probably use a nn (I like Kit), but Catherine isn't so long that it needs a nn. KATH-rin (which is how I tend to say it) sounds no longer than most nns--Annie, Lily, etc. Katie or Kitty is as many syllables as the full name. It looks long, but it doesn't sound that long. If that makes sense. I like some of your other options more (particularly Emilia!), but Catherine is so beautiful; I adore it. I'm not exactly sure where it falls on my list, but I would be happy to have a Catherine "Kit" someday! As for Catherine vs. Charlotte... I'm torn. Charlotte is technically higher on my list, and I ADORE the nns Lola and Lottie, but I like that Catherine's less expected and overdone these days. Plus, it's still strong and feminine and just all around wonderful. I would love to have a daughter with either name, but I don't think I'd use both. Catherine Elena doesn't really wow me as a combo anymore (used to LOVE it, though!), but it is lovely. And Catherine Elena V-ickory flows well. I think it'd be a lovely name. I think I've just grown to expect you to have a little Emilia Catherine (which is, och, so beautiful and utterly swoonworthy!) that I can't really see you using any other name. Catherine up front is really lovely, though, and I do adore it.
I love Catherine! It's so classic and elegant. I think sometimes the quest for a unique name has us labeling names like Catherine as boring just because they have a long history, if that makes sense. When the whole classroom is full of Kaylas, Olivias, Sophias, and every Aiden name you can think of, Catherine will not look at all boring, but will also not be out of place, which I think is a great balance to strike. :-) I personally prefer the Katharine spelling, but Catherine is lovely too.
I find Catherine boring. I grew up with three of them also (80's). I do prefer C spelling over K though.
Catherine is timeless and classy. It used to be a name I was unsure about but now I love it, it's beautiful. I think both names though sound fine with your surname. I like Charlotte mostly for the nn Lottie which I just seem to love. I prefer Catherine though and she doesn't have to have a nickname as it's nice on it's own.
Also, great middle name choice, Elena is my favourite name atm. :)
Catherine, to me, is like vanilla ice cream. Always sweet and pleasant, but sometimes I just crave something more.