We explore the interplay of electron-electron correlations and surface effects in the prototypical correlated insulating material, NiO. In particular, we compute the electronic structure, magnetic properties, and surface energies of the $(001)$ and $(110)$ surfaces of paramagnetic NiO using a fully charge self-consistent DFT+DMFT method. Our results reveal a complex interplay between electronic correlations and surface effects in NiO, with the electronic structure of the $(001)$ and $(110)$ NiO surfaces being significantly different from that in bulk NiO. We obtain a sizeable reduction of the band gap at the surface of NiO, which is most significant for the $(110)$ NiO surface. This suggests a higher catalytic activity of the $(110)$ NiO surface than that of the $(001)$ NiO one. Our results reveal a charge-transfer character of the $(001)$ and $(110)$ surfaces of NiO. Most notably, for the $(110)$ NiO surface we observe a remarkable electronic state characterized by an alternating charge-transfer and Mott-Hubbard character of the band gap in the surface and subsurface NiO layers, respectively. This novel form of electronic order stabilized by strong correlations is not driven by lattice reconstructions but of purely electronic origin. We notice the importance of orbital-differentiation of the Ni $e_g$ states to characterize the Mott-Hubbard insulating state of the $(001)$ and $(110)$ NiO surfaces. The unoccupied Ni $e_g$ surface states are seen to split from the lower edge of the conduction band to form strongly localized states in the fundamental gap of bulk NiO. Our results for the surface energies of the $(001)$ and $(110)$ NiO surfaces show that the $(001)$ facet of NiO has significantly lower energy. This implies that the relative stability of different surfaces, at least from a purely energetic point of view, does not depend on the presence or absence of magnetic order in NiO.