Quasi-normal oscillation modes of neutron stars provide a means to probe their interior composition using gravitational wave astronomy. We compute the frequencies and damping times of composition-dependent core g-modes of neutron stars containing quark matter employing linearized perturbative equations of general relativity. We find that ignoring background metric perturbations due to the oscillating fluid, as in the Cowling approximation, underestimates the g-mode frequency by up to 10% for higher mass stars, depending on the parameters of the nuclear equation of state and how the mixed phase is constructed. The g-mode frequencies are well-described by a linear scaling with the central lepton (or combined lepton and quark) fraction for nucleonic (hybrid) stars. Our findings suggest that neutron stars with and without quarks are manifestly different with regards to their quasi-normal g-mode spectrum, and may thus be distinguished from one another in future observations of gravitational waves from merging neutron stars.