The scarcity of natural aggregates and the accumulation of oil sludge in desert regions pose critical challenges for highway construction. Although aeolian sand and oil sludge pyrolysis residue have been studied individually as construction materials, their combined use in foamed lightweight soil remains unexplored. This study addresses this gap by developing a novel foamed lightweight soil termed SOFS, which is created through the synergistic modification of aeolian sand and oil sludge pyrolysis residue. A six-factor, five-level orthogonal array (L25) was employed to systematically investigate the effects of residue content, sand content, foam-to-slurry ratio, foaming agent dilution, water-to-solid ratio, and mixing time. The evaluated properties included physical properties (fluidity and wet density), mechanical properties (compressive, splitting tensile, and flexural strength), and durability (wet–dry and freeze–thaw resistance). Scanning electron microscopy was used to examine the microstructural mechanisms. Variance and range analysis identified the optimal mixture, designated H14, which achieved 28-day compressive, splitting tensile, and flexural strengths of 3.75 MPa, 2.21 MPa, and 0.9 MPa, respectively, thereby meeting desert roadbed requirements. Compared with conventional materials, H14 exhibited superior durability, with strength losses of only 16.3% in compressive strength and 19.1% in splitting tensile strength after 25 cycles. Microstructural analysis revealed a dense C-S-H gel network encapsulating the solid waste particles, with nanoscale Al- and Cl-rich crystalline phases observed at interfacial pores—a phenomenon that has rarely been documented in previous studies. These findings provide a theoretical and technical foundation for solid waste valorization and the development of sustainable desert infrastructure.