This study investigates the development of all-solid-waste binder materials based on phosphogypsum (PG), slag, recycled cement powder (RCP), and red mud (RM), with quicklime serving as the activator. The individual and synergistic contributions of RCP and RM to mechanical properties, durability, and microstructure are systematically evaluated. Results show that the mixture containing 10% RCP + 10% RM exhibits the best overall performance. The 28-day compressive, flexural, and splitting tensile strengths reached 43.2 MPa, 7.4 MPa, and 4.0 MPa, respectively, representing increases of 57.1%, 57.4%, and 42.9%, compared with the PG-GGBS reference system. In addition, durability performance was markedly improved. The chloride diffusion coefficient decreased by 42.5%, drying shrinkage was reduced by 43.6%, and the freeze–thaw resistance limit increased from 100 to 175 cycles. Microstructural analysis revealed that RCP acts primarily as a micro-filler while providing reactive mineral phases and nucleation sites that promote hydration. Meanwhile, RM enhances system alkalinity and introduces additional aluminosilicate minerals, thereby accelerating precursor dissolution and polymerization. RM also activates the latent reactivity of RCP, generating secondary pozzolanic reactions. Together, RCP and RM synergistically promote the formation of additional C-(A)-S-H gel while maintaining adequate AFt production, achieving a balanced hydration system that refines the pore structure and enhances macroscopic performance. The developed binder demonstrates excellent overall performance and effective solid-waste utilization, highlighting its strong potential for eco-friendly construction applications. Furthermore, it provides valuable insights into the advancement of sustainable solid-waste-based building materials.