The structures and thermal evolutions of the large icy satellites of the outer solar system are considered. It is shown (for bodies comparable in size and mass to the Galilean satellites, having sizeable mass fraction of H2O, and with meteoritic abundances of radioactive materials contained within their silicate fractions) that the crust of solid ice over a liquid mantle predicted by conductive heat-transfer calculations is unstable to large-scale solid-state convection. For appropriate material parameters, convective heat-transfer rates are sufficient to freeze a large liquid mantle on a time scale that is short compared to the lifetime of the body. It is also concluded that the ice layer is convecting at the present time. A reevaluation of previous work, using improved values for material parameters and boundary conditions, reverses earlier conclusions and implies a rigid outer crust with resulting long-term stability of surface features to creep deformation. The combination of a rigid crust with active internal convection presents the additional possibility of surface features that are produced and maintained by dynamic internal processes.