I also have to say Carnival - though it has been a few years since I sailed on them. They come accross as surprisingly good.
However - it is important to mention that for alternative dining it is hard to beat NCL with their 10 restaurants on board. I will tell you their Japanese food is wonderful. The food in the Le Bistro was excellent, too. But we are talking about regular restaurant food.