We've sailed ....
... 15+ times depending on whether you ask me or my spouse who has sailed 17 times. And as such we've been on DCL 3x, RCCL, CCL, HAL, NCL, Rennisance which was reborn as Oceania Cruise Line and a Yangzee river boat. As such, we heard that travel agents avoid NCL because they do not compensate TAs like the other cruise lines. AND... our experience with NCL was rather good. We had 41 people in my group... I was the organizer and host for 20 of the 41 who work for me. The other 21 comprised my family with a few expanded family members and a couple of friends.
I found the dining and service to be on a par with any other comparable line. And the private dining experience was rather good with individual made to order dishes and 1st rate service. Aside from that... the ship was as much of a "destination" as a RCCL ship would be... for the most part. Of course, some RCCL ships can boast of some singular atractions ... such as the rock climbing, the ice rink, and I head they're building one with a surf machine. Aside from that... I think there is more in common then distict between the two. The overall experience was quite good with NCL though and I would not hesitate to consider them. The freestyle dining was a definate advantage... and the old Rennisance line had that same feature.
Now we have never sailed Celebrity or Princess... and I have heard appealing things about these lines. So... I think that you should open up to consider any line with the newest ships that sails a route which appeals to you two.
And may I ask weter you have any more specific questions?