Plant growth-promoting bacteria (PGPB) are crucial for sustainable agriculture, offering an eco-friendly alternative to chemical fertilizers by boosting crop productivity. This research focused on developing cost-effective culture media for PGPB associated with sugarcane, utilizing agro-industrial byproducts. We evaluated 83 formulations based on sugarcane molasses, glycerin, corn steep liquor, and yeast extract for eight Bacillus species and six diazotrophic species. For the Bacillus genus, the optimal medium consisted of glycerin (2%), corn steep liquor (1.5%), and yeast extract (0.35%)—this formulation yielded a high optical density (OD_600nm) of 9.36 ± 0.17 within 48 hours for Bacillus megaterium (Bm). For the diazotrophic bacteria, the most effective medium was composed of sugarcane molasses (2%), corn steep liquor (3%), and yeast extract (0.5%), supplemented with macro- and micronutrients, and vitamins, achieving an OD_600nm of 8.416 ± 0.016 in 48 hours for Herbaspirillum rubrisubalbicans (Hr). In comparison to the standard Luria–Bertani (LB) medium, which resulted in turbidities of 4.46 ± 0.22 for Bm and 3.19 ± 0.04 for Hr, our developed media demonstrated a more than twofold increase in bacterial growth. These findings highlight a promising, sustainable approach to producing high-density PGPB inoculants for enhanced agricultural productivity.