Max Metlitski University of California, Santa Barbara (UC Santa Barbara) A 3d electron topological insulator (ETI) is a phase of matter protected by particle-number conservation and time-reversal symmetry. It was previously believed that the surface of an ETI must be gapless unless one of these symmetries is broken. A well-known symmetry-preserving, gapless surface termination of an ETI supports an odd number of Dirac cones. In this talk, I will show that in the presence of strong interactions, an ETI surface can actually be gapped and symmetry preserving, at the cost of carrying an intrinsic two-dimensional topological order. I will argue that such a topologically ordered phase can be obtained by depositing an s-wave superconductor on the ETI surface and then proliferating the flux 2hc/e vortex. The resulting topological order consists of two sectors: a Moore-Read sector, which supports non-Abelian charge e/4 anyons, and an Abelian anti-semion sector, which is electrically neutral. The time-reversal and particle number symmetries are realized in this surface phase in an "anomalous" way: one which is impossible in a strictly 2d system. If time permits, I will discuss related results on topologically ordered surface phases of 3d topological superconductors.