Implementing tire rubber-concrete mixtures to produce sandwich-structured cementitious composites can represent an attractive route in the perspective of lightweight design, energy efficiency, and sustainability for the building and construction industry. This work deals with a DOE multi-response optimization study on rubber-concrete mixes designed with different proportions of fine and coarse rubber aggregates to achieve the best formulation to be applied in the manufacturing of cementitious sandwich composites. The “sand-free” concrete mixture made up of 70% of rubber powder and 30% of rubber granules was optimal in terms of mechanical properties, physical characteristics, and thermo-acoustic insulation behavior. Sandwich-structured composite incorporating the optimum mix as a core layer showed significant improvement in terms of flexural performance over the monolithic rubberized materials and strength value in the range of RILEM “class II” lightweight construction materials.