In the saline, cold, and arid regions of Western China, the adhesive performance at the carbon fiber-reinforced polymer (CFRP)-concrete interface critically affects the long-term reliability of CFRP-strengthened structures. Replacing the organic epoxy resin (EP) with inorganic magnesium phosphate cement (MPC) has been proposed as an alternative. However, comparative studies on the deterioration of MPC- and EP-bonded CFRP-concrete under sulfate freeze-thaw cycles are limited. This study employed double-shear tests to systematically compare the failure modes, ductility, and bond performance of the CFRP-concrete interface bonded with MPC and EP after 25, 50, and 75 sulfate freeze-thaw cycles. The results indicate that, as the number of cycles increased, MPC-bonded specimens exhibited progressive interfacial peeling, whereas EP-bonded specimens underwent abrupt brittle fracture. At 0, 25, 50, and 75 cycles, the peak strains of MPC specimens exceeded those of EP specimens by 9.28%, 10.13%, 5.99%, and 0.86%, respectively, indicating greater ductility. Bond performance declined markedly for both groups as cycles increased, with MPC specimens showing greater deterioration. After 75 cycles, compared with EP-bonded specimens, MPC-bonded specimens showed a 16.56% lower interfacial load capacity, a 21.53% reduction in peak bond stress, and a 6.03% shorter effective bond length. This systematic comparison of MPC- and EP-bonded CFRP-concrete under sulfate freeze-thaw exposure provides guidance for adhesive selection and strengthening practices in saline, cold, and arid regions.