Modern radar systems are expected to operate reliably in congested environments. A candidate technology for meeting these demands is frequency agile radar (FAR), which randomly changes its carrier frequencies. FAR is known to improve the electronic counter-countermeasures (ECCM) performance while facilitating operation in congested setups. To enhance the target recovery performance of FAR in complex electromagnetic environments, we propose two radar schemes extending FAR to multi-carrier waveforms. The first is Wideband Multi-carrier Agile Radar (WMAR), which transmits/receives wideband waveforms simultaneously with every antenna. To mitigate the demanding hardware requirements associated with wideband waveforms used by WMAR, we next propose multi-Carrier AgilE phaSed Array Radar (CAESAR). CAESAR uses narrowband monotone waveforms, thus facilitating ease of implementation of the system, while introducing {\em spatial agility}. We characterize the transmitted and received signals of the proposed schemes, and develop an algorithm for recovering the targets, based on concepts from compressed sensing to estimate the range-Doppler parameters of the targets. We then derive conditions which guarantee their accurate reconstruction. Our numerical study demonstrates that both multi-carrier schemes improve performance compared to FAR while maintaining its practical benefits. We also demonstrate that the performance of CAESAR, which uses monotone waveforms, is within a small gap from the wideband radar.