The presence of quark matter in neutron stars may affect several neutron star observables and the neutrino signal in core-collapse supernovae. These observables are sensitive to the phase of quark matter that is present in compact objects. We present the first calculation of the phase structure of dense quark matter which includes a six-fermion color-superconducting interaction and show that the effect of this term can destabilize the pairing interaction, favoring phases where fewer quarks are paired. In turn, this modification of the phase structure can modify the neutrino signal, the structure of the neutron star, and the long-term cooling. We also show that, contrary to the 20-year old paradigm of the surface structure of the "strange-quark stars", the surface of these objects may consist of nuggets of strange quark matter screened by the electron gas.