  We present the full details of a calculation at next-to-leading order of the
momentum diffusion coefficient of a heavy quark in a hot, weakly coupled, QCD
plasma. Corrections arise at O(g_s); physically they represent interference
between overlapping scatterings, as well as soft, electric scale (p ~ gT) gauge
field physics, which we treat using the hard thermal loop (HTL) effective
theory. In 3-color, 3-flavor QCD, the momentum diffusion constant of a
fundamental representation heavy quark at NLO is kappa = (16\pi/3) alpha_s^2
T^3 (log(1/g) + 0.07428 + 1.9026 g). We extend the computation to a heavy
fundamental representation ``probe'' quark in large N_c, N=4 Super Yang-Mills
theory, where the result is kappa^{SYM}= (lambda^2 T^3)(6\pi)
(log(1/\sqrt{\lambda}) + 0.4304 + 0.8010 \sqrt{lambda}) (where lambda=g_s^2 N_c
is the t'Hooft coupling). In the absence of some resummation technique, the
convergence of perturbation theory is poor.
