Hi
im in the same position as you as i have an 18 and 15 year old boy and girl, i have been looking and have found princess cruises are ideal as they have 2 double rooms with twin beds in one and a double in other with an inter-connecting door so ensures complete privacy but safety leaving them too. The only problem is they are at the higher end of the market and am hopeing that when the brochures come out tomorrow for next year that they may have discounts.
Goodluck.