I think a cruise would be very romantic. Imagine yourselves out there at night looking at the clear sky able to see all the stars as if you could touch them. You're holding each other cuddling, drinking wine or what have you, while watching the tides of the ocean roll in and out. It could make you two feel like you're the only people on the planet. Something couples normally enjoy