Your comment on a medium for light is the key. The diffusion of light by a medium dictates what we see and don't see - whether something has color or is black. The diffusion of sunlight accounts for the blue appearance of the sky and reddish appearance of the sun at sunset. In essence, the atmosphere of planets like earth allows color until we reach its outer rim and then diffusion stops and it becomes black. The light from distant stars appears red because it is diffused by fine dust particles distributed throughout space.
Space appears dark or black due to absence of a medium to diffuse light.