This study aims to provide a high-value and environmentally friendly method for the application of coal-based solid waste. Modified fly ash/polyurethane (MFA/PU) and modified coal gangue powder/polyurethane (MCG/PU) composites were prepared by adding different contents of MFA and MCG (10%, 20%, 30%, 40%). At the filler content of 30%, the compressive strengths of MFA/PU and MCG/PU are 84.1 MPa and 46.3 MPa, respectively, likely due to an improvement in interface compatibility, as indicated by scanning electron microscopy (SEM). The MFA/PU and MCG/PU composites present their highest limiting oxygen index (LOI) values of 29% and 23.5%, respectively, when their filler content is 30%. MFA has advantages in improving the LOIs of composites. Cone calorimetry (CCT) and SEM demonstrate that the two composites exhibit similar condensed-phase flame-retardant behaviors during combustion, which releases CO2 in advance and accelerates the formation of a dense barrier layer. Compared with the MFA/PU composites, the MCG/PU composites could produce a more stable and dense barrier structure. Water quality tests show that heavy metals do not leak from FA and CG embedded in PU. This work provided a new strategy for the safe and high-value recycling of coal-based solid waste.