The transport of a single nanoparticle in unentangled and entangled polymer melts is studied based on a microscopic, force-level, self-consistent generalized Langevin equation approach. Nanoparticle self-motion and length-scale-dependent polymer relaxation enter as two parallel and competing channels of force relaxation. For entangled melts, particle long-time mobility exhibits size-dependent non-StokesEinstein behaviors controlled by (i) fast diffusion and length-scale-dependent collective relaxation of the unentangled matrix for particles smaller than the tube diameter and (ii) polymer relaxation via reptation for nanoparticles larger than the tube diameter. The two regimes are connected by a relatively sharp but continuous crossover. Recovery of hydrodynamic behavior requires the nanoparticle to be roughly 10 times larger than the tube diameter. Theoretical predictions for the diffusion constant are in good agreement with recent simulations of unentangled and lightly entangled melts, including the crossover regime where the nanoparticle and tube diameters are roughly equal. The calculations are also in reasonable accord with several experiments in entangled synthetic polymer melts and DNA solutions, although the activated hopping motion not included in the present theory may be important in a narrow intermediate crossover regime for sufficiently entangled polymers. The predictions of the theory for intermediate-time anomalous diffusion are of mixed quality based on comparison to simulations. The significant limitations identified are associated with our minimalist treatment of collective density fluctuation relaxation on intermediate time and length scales, including the possible importance of non-reptation relaxation processes in entangled melts.