Find Your Cruise
Go on any of the Vouyger class of ships from Royal caribean, they are fantastic for children, you can virtual walk the ship on RCI's web site.
P&O now have four child friendly ships, Oceana, Oriana, Aurora and the brand new Ventura. Many reviews on this site to give you an idea of how good.
Have looked around NCL Gem and the kids facilities looked great but not quite as extensive as Royal Caribbean. However with freestyle dining you don't need to dress up for dinner or have set dining times, so not as formal as P&O/ Royal Caribbean.
Royal Caribbean are generally accepted to be the best ships for children, although I have heard that Ventura's childrens area is good.