We just did our first cruise, also a 4-night and my kids (4 and 7) really enjoyed the Blackbeard Cay excursion at Nassau. Next time, we'll probably book a room at Atlantis, though, just to do something different.
It was our 10th anniversary and I got the Romantic Escape at Sea package, which included the couples massage, champagne breakfast, gift basket and Palo reservations. My DH was very impressed, especially with the rose petal turndown on the Palo night!! He loved the spa time also. I would highly recommend that package.
Stacy