We introduce a new multimode cavity QED architecture for superconducting circuits which can be used to implement photonic memories, more efficient Purcell filters, and quantum simulations of photonic materials. We show that qubit interactions mediated by multimode cavities can have exponentially improved contrast for two qubit gates without sacrificing gate speed. Using two-qubits coupled via a three-mode cavity system we spectroscopically observe multimode strong couplings up to 102MHz and demonstrate suppressed interactions off-resonance of 10kHz when the qubits are ~600MHz detuned from the cavity resonance. We study Landau-Zener transitions in our multimode systems and demonstrate quasi-adiabatic loading of single photons into the multimode cavity in 25ns. We introduce an adiabatic gate protocol to realize a controlled-Z gate between the qubits in 95ns and create a Bell state with 94.7% fidelity. This corresponds to an on/off ratio (gate contrast) of 1000.