  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 paper we
deduce a symmetry-respecting, gapped surface termination of an ETI, which
carries an intrinsic 2d topological order, Moore-Read x anti-semion. The
Moore-Read sector supports non-Abelian charge 1/4 anyons, while the Abelian,
anti-semion sector is electrically neutral. Time-reversal symmetry is
implemented in this surface phase in a highly non-trivial way. Moreover, it is
impossible to realize this phase strictly in 2d, simultaneously preserving its
implementation of both the particle number and time-reversal symmetries. A 1d
edge on the ETI surface between the topologically-ordered phase and the
topologically trivial time-reversal-broken phase with a Hall conductivity
sigma_H = 1/2, carries a right-moving neutral Majorana mode, a right-moving
bosonic charge mode and a left-moving bosonic neutral mode. The
topologically-ordered phase is separated from the surface superconductor by a
direct second order phase transition in the XY* universality class, which is
driven by the condensation of a charge 1/2 boson, when approached from the
topologically-ordered side, and proliferation of a flux 4\pi-vortex, when
approached from the superconducting side. In addition, we prove that
time-reversal invariant (interacting) electron insulators with no intrinsic
topological order and electromagnetic response characterized by a \theta-angle,
\theta = \pi, do not exist if the electrons transform as Kramers singlets under
time-reversal.
