Lanthanide-doped nanocrystals (NCs) differ from their bulk counterparts due to their large surface to volume ratio. It is generally assumed that the optical properties are not affected by size effects as electronic transitions occur within the well-shielded 4f shell of the lanthanide dopant ions. However, defects and disorder in the surface layer can affect the luminescence properties. Trivalent europium is a suitable ion to investigate the subtle influence of the surface, because of its characteristic luminescence and high sensitivity to the local environment. Here, we investigate the influence of disorder in NCs on the optical properties of lanthanide dopants by studying the inhomogeneous linewidth, emission intensity ratios, and luminescence decay curves for LaPO4:Eu3+ samples of different sizes (4 nm to bulk) and core-shell configurations (core, core-isocrystalline shell, and core-silica shell). We show that the emission linewidths increase strongly for NCs. The ratio of the intensities of the forced electric dipole (ED) and magnetic dipole (MD) transitions, a measure for the local symmetry distortion around Eu3+ ions, is higher for samples with a large fraction of Eu3+ ions close to the surface. Finally, we present luminescence decay curves revealing an increased nonradiative decay rate for Eu3+ in NCs. The effects are strongest in core and core-silica shell NCs and can be reduced by growth of an isocrystalline LaPO4 shell. The present systematic study provides quantitative insight into the role of surface disorder on the optical properties of lanthanide-doped NCs. These insights are important in emerging applications of lanthanide-doped nanocrystals.