Get them involved in the planning. Let them have a stake in it. Discuss and select the shore excursions as a family. Talk about dining options with them--early, late, your family alone or big table with others. Have them study deck plans; ask their opinions; what shipboad acitvities look good to them.
Half the fun of a cruise is in the planning and anticipation. If they see you getting excited about, they'll get excited about. Teenagers like to act like it's not cool to like things their parents like--but they will follow your example.
From looking at the Celebrity Web site, I see you will be going to Venice, Italy; Dubrovnik, Croatia; Athens (Piraeus), Greece; Santorini, Greece; Naples/Capri, Italy; Florence, Italy; Rome (Civitavecchia), Italy; Nice (Villefranche), France; and Barcelona, Spain.
I agree with f-mattox to involve your teens in the planning, both for the ship and ports. As they might not want to read through tour books (my son doesn't), perhaps you might rent for them some popular movies that were filmed in some of these locales. That should get the excitement going.
Once on board, your cabin will receive a daily program listing the events for the day and evening. Seek their opinions in making those onboard plans. Extra copies are available near the purser's desk (bottom of the grand staircase), so they can each have one. (Or, you can ask your cabin steward to provide extra copies each day.)
The only downside I can anticipate is that there are some activities your 18-year-old will be able to enjoy, but the 16-year-old won't. One of these is the relaxing Thalassotherapy pool outside the spa (although your younger teen can enjoy the rest of the spa).
Still, it sounds like a wonderful family vacation, and I am sure you will create many great memories.
The Millenium has activities posted daily for most age groups. I think your family is in for a wonderful vacation. I know we enjoyed the swimming pool and the hydropool. I just returned on June 7 and loved the Millie. Met some fine folks and am still daydreaming about the beautiful places we saw.
Celebrity is a touch choice for teenagers. With the exception of breaks, i.e, spring,Christmas and so forth the guests lean to the older crowd, 50+. My two teens, 19 and 21 had to rely on conversations with crew members. You might have a better go at it because it's summer. Let me know how it goes as we have given up on them due to the age factor. Great line however.
Jelly, i'll let you know how we get on re mixing with other people of their age. Before booking I asked Celebrity re the age profile and they thought it would be varied due to the time of year with school hols etc.
Lisa thanks for the info re the formal dress, i'l arrange a dark suit and tie as I can't see the 12 year old going further than that!