The optical afterglow of long-duration GRB 071003 is among the brightest yet to be detected from any GRB, with R ≈ 12 mag in KAIT observations starting 42 s after the GRB trigger, including filtered detections during prompt emission. However, our high-S/N afterglow spectrum displays only extremely weak absorption lines at what we argue is the host redshift of z = 1.60435, in contrast to the three other, much stronger Mg II absorption systems observed at lower redshifts. Together with Keck adaptive optics observations, which fail to reveal a host galaxy coincident with the burst position, our observations suggest a halo progenitor and offer a cautionary tale about the use of Mg II for GRB redshift determination. We present early- through late-time observations spanning the electromagnetic spectrum, constrain the connection between the prompt emission and early variations in the light curve (we observe no correlation), and discuss possible origins for an unusual, marked rebrightening that occurs a few hours after the burst: likely either a late-time refreshed shock or a wide-angle secondary jet. Analysis of the late-time afterglow is most consistent with a wind environment, suggesting a massive star progenitor. Together with GRB 070125, this may indicate that a small but significant portion of star formation in the early universe occurred far outside what we consider a normal galactic disk.