Concrete aggregates made of expanded polystyrene (EPS) have been more popular due to the rising need for lightweight and energy-efficient building materials. However, its incorporation often reduces mechanical strength, limiting structural applications. Prior studies suggest surface treatments can enhance interfacial bonding. The study explores the mechanical performance of lightweight concrete containing EPS beads treated with a fly ash-based coating, with a primary focus on the modulus of elasticity and its correlation with compressive and split tensile strengths. Concrete samples were prepared using both uncoated and coated EPS beads. Cube specimens were tested for compressive strength at 7, 14, 28, and 56 days, whereas cylinder specimens were tested at 28 days. Due to inconsistencies in stress–strain data that hindered direct calculation, the empirical Eurocode 2 equation was implemented to estimate the modulus of elasticity. Results indicate that coated EPS concrete (MEPS) exhibits a 24–33% increase in compressive strength over uncoated EPS concrete. Nevertheless, its compressive strength remains 66–70% lower than conventional concrete. Split tensile strength also improved with coating treatment. Although EPS concrete has a lower modulus of elasticity, this property might enhance its flexibility and energy absorption, which can help mitigate cracking in non-load-bearing elements—an advantage in certain wall applications. MEPS concrete satisfies the minimum mechanical requirements for non-structural use and offers potential benefits in energy-efficient building design. Its reduced density, improved strength, and inherent deformability make it a promising candidate for lightweight, insulating wall construction in modern sustainable architecture.