When it became evident that light was made of waves, after Young's double slit experiments (1801 as I recall), the only waves anybody knew anything about were all mechanical waves (sound waves, ocean waves, & etc.) They were mechanical vibrations. So everyone just assumed that light waves were also mechanical vibrations in something they called the "lumeniferous ether". But the speed of a mechanical wave depends on the stiffness of the medium, stiffer media supporting faster waves. So the ether had to be really weird, stiff enough to support amazingly fast light waves (far stiffer than any known material), yet allowing Earth to gently glide through. Nobody could ever make physical sense of this ether stuff, but they couldn't do without it either, since all waves were known to be mechanical vibrartions.

But Maxwell killed the ether by showing that light was a wave of electromagnetic field, not a mechanical vibration. The ether became instantly unnecessary. And since nobody ever was able to figure out how anything with such strange properties could exist anyway, they were not hesitant in doing away with it altogether. The waves of electromagnetism could propagate through the "emptiness" of space without the need for mechanical support.

Einstein killed the idea of "empty" space by imbuing space (or space-time) with "physical" properties, such as geometry and a limited ability to sustain energy per unit volume (a black hole is a symptom of the "mechanical" failure of space-time due to energy overload).

And quantum mechanics came right behind Einstein, in granting the "emptiness" of space the power to exercise zero-point energy, vacuum fluctuations & virtual particles. So now we think of the "emptiness" of space as an energetic & dynamic environment. In fact, "empty" is simply no longer an acceptable description of space (or space-time).

So, what kind of medium is space? I don't think anyone can answer the question in a literal sense. The best we can do is to describe its behavior, as implied by the various physical theories, like quantum mechanics & general relativity. Curvature is both mathematical and physical (it is mathematically described and has physically observable consequences). The expansion of the universe causes the curvature of space (as measured, say, at a given point) to be time-variable. So, as we see it, the space through which the photon propagates stretches out as the photon moves through, stretching the photon (relative to us), a necessary consequence of the fact that "space" is the basis for coordinate measure.

Ah, so you might ask, if the photon's energy depends on its frequency, and we lower the frequency (by making the wavelength longer), where does the energy go? The answer is nowhere. All you have to do is speed up towards the photon, adding an extra blueshift, and voilá, you measure a photon with just the same energy it had when it left the distant galaxy (if you can speed up enough). The energy of a photon depends on the reference frame of the observer who measures it, and not on the photon itself.

There is a great lesson to learn from relativity and quantum mechanics: It's all about observers & reference frames.

Cheers.