Several different classes of trans-Neptunian objects (TNOs) have been identified based on their optical and near-infrared colors. As part of the Colours of the Outer Solar System Origins Survey (Col-OSSOS), we have obtained g-, r-, and z-band photometry of 26 TNOs using Subaru and Gemini Observatories. Previous color surveys have not utilized z-band reflectance, and the inclusion of this band reveals significant surface reflectance variations between sub-populations. The colors of TNOs in g − r and r − z show obvious structure, and appear consistent with the previously measured bi-modality in g − r. The distribution of colors of the two dynamically excited surface types can be modeled using the two-component mixing models from Fraser & Brown. With the combination of g − r and r − z, the dynamically excited classes can be separated cleanly into red and neutral surface classes. In g − r and r − z, the two dynamically excited surface groups are also clearly distinct from the cold classical TNO surfaces, which are red, with $g-r\gtrsim 0.85$ and r − z lesssim 0.6, while all dynamically excited objects with similar g − r colors exhibit redder r − z colors. The z-band photometry makes it possible for the first time to differentiate the red excited TNO surfaces from the red cold classical TNO surfaces. The discovery of different r − z colors for these cold classical TNOs makes it possible to search for cold classical surfaces in other regions of the Kuiper Belt and to completely separate cold classical TNOs from the dynamically excited population, which overlaps in orbital parameter space.