Both physical and dynamical properties must be considered to constrain the origins of the dynamically excited distant Solar System populations. We present high-precision (g-r) colors for 25 small (Hr>5) dynamically excited Trans-Neptunian Objects (TNOs) and centaurs acquired as part of the Colours of the Outer Solar System Origins Survey (Col-OSSOS). We combine our dataset with previously published measurements and consider a set of 229 colors of outer Solar System objects on dynamically excited orbits. The overall color distribution is bimodal and can be decomposed into two distinct classes, termed `gray and `red, that each has a normal color distribution. The two color classes have different inclination distributions: red objects have lower inclinations than the gray ones. This trend holds for all dynamically excited TNO populations. Even in the worst-case scenario, biases in the discovery surveys cannot account for this trend: it is intrinsic to the TNO population. Considering that TNOs are the precursors of centaurs, and that their inclinations are roughly preserved as they become centaurs, our finding solves the conundrum of centaurs being the only outer Solar System population identified so far to exhibit this property (Tegler et al. 2016). The different orbital distributions of the gray and red dynamically excited TNOs provide strong evidence that their colors are due to different formation locations in a disk of planetesimals with a compositional gradient.