By employing rheological experiments, mode coupling theory, and computer simulations based on realistic coarse-grained models, we investigate the effects of small, hard colloids on the glassy states formed by large, soft colloids. Multiarm star polymers mimic hard and soft colloids by appropriately varying the number and size of their arms. The addition of hard colloids leads, depending on their concentration, to either melting of the soft glass or the emergence of two distinct glassy states. We explain our findings by depletion of the colloids adjacent to the stars, which leads to an arrested phase separation when the repulsive glass line meets the demixing binodal. The parameter-free agreement between experiment, theory, and simulations suggests the generic nature of our results and opens the route for designing soft-hard colloidal composites with tunable rheology.