Royal Caribbean are not too formal but where parents want a break kids can eat with the kids club, however if you have a small dining table you will find lots of parents take small children into the main didning room and the waiters are genrally excellent with little children. Of course the Windjammer resturant can be used self service in the evenings too. I have done ocean village and royal caribbean and rate the latter as the best for adults and kids especially the new Freedon class ships both in the Caribbean and Med. Also I have to say from a safety point of view for mobile toddlers the newest ships have very few rails apart from on the very top deck with most decks being edged with safe high perspex sides as opposed to those tempting to climb traditional railings, but watch the main pool depths though, that's the only real small child hazard I have seen on The Freedon & liberty of the seas. Shop around RCI early booking deals are as good if not sometimes better than the late deals and I wouldn't worry about balcony cabins, the inside and outside cabins with third beds are ideal when sharing with children.
Thankyou collins on your reply to my question, it really has helped us in making a choice on our cruise.
Try princess ships,avoid thomson ships at all costs.they cater for children but are old,dated,grubby,the cabins are small and drab with formica teak furniture.