Recent observations of the ultra-hot Jupiter WASP-76b have revealed a diversity of atmospheric species. Here we present new high-resolution transit spectroscopy of WASP-76b with GRACES at the Gemini North Observatory, serving as a baseline for the Large and Long Program Exploring the Diversity of Exoplanet Atmospheres at High Spectral Resolution (Exoplanets with Gemini Spectroscopy, or ExoGemS for short). With a broad spectral range of $400 - 1050$ nm, these observations allow us to search for a suite of atomic species. We recover absorption features due to neutral sodium (Na I), and report a new detection of the ionized calcium (Ca II) triplet at ~ $850$ nm in the atmosphere of WASP-76b, complementing a previous detection of the Ca II H & K lines. The triplet has line depths of $0.295 pm 0.034$% at ~ $849.2$ nm, $0.574 pm 0.041$% at ~ $854.2$ nm, and $0.454 pm 0.024$% at ~ $866.2$ nm, corresponding to effective radii close to (but within) the planets Roche radius. These measured line depths are significantly larger than those predicted by model LTE and NLTE spectra obtained on the basis of a pressure-temperature profile computed assuming radiative equilibrium. The discrepancy suggests that the layers probed by our observations are either significantly hotter than predicted by radiative equilibrium and/or in a hydrodynamic state. Our results shed light on the exotic atmosphere of this ultra-hot world, and will inform future analyses from the ExoGemS survey.