  It is known that the classical $O(N)$ model in dimension $d > 3$ at its bulk
critical point admits three boundary universality classes: the ordinary, the
extra-ordinary and the special. For the ordinary transition the bulk and the
boundary order simultaneously; the extra-ordinary fixed point corresponds to
the bulk transition occurring in the presence of an ordered boundary, while the
special fixed point corresponds to a boundary phase transition between the
ordinary and the extra-ordinary classes. While the ordinary fixed point
survives in $d = 3$, it is less clear what happens to the extra-ordinary and
special fixed points when $d = 3$ and $N \ge 2$. Here we show that formally
treating $N$ as a continuous parameter, there exists a critical value $N_c > 2$
separating two distinct regimes. For $N < N_c$ the extra-ordinary fixed point
survives in $d = 3$, albeit in a modified form: the long-range boundary order
is lost, instead, the order parameter correlation function decays as a power of
$\log r$. In particular, for $N=2$, starting in the surface phase with
quasi-long-range order and approaching the bulk phase transition, the stiffness
of the surface order parameter diverges logarithmically. For $N > N_c$ there is
no fixed point with order parameter correlations decaying slower than power
law; we discuss two scenarios for the evolution of the phase diagram past $N =
N_c$. Our findings appear to be consistent with recent Monte-Carlo studies of
classical models with $N = 2$ and $N = 3$. We also compare our results to
numerical studies of boundary criticality in 2+1D quantum spin models.
