So in the galaxy's reference frame it is stationary, so from its point of view it should emit un-shifted light with energy $E$ and speed $c$.
This is correct. The part you have confused is:
Regardless of how fast we are going with respect to the originating galaxy, the photon moves at speed $c$ and has energy $E$ when we observe it.
The observed energy depends on your relative motion to the source.
The energy of a photon relates to its frequency by $E = hf$.
The speed of a photon relates to its frequency by $v = \lambda f$ with $v = c$.
You can see that because $v$ must be a constant for all observers, the only element that can change is $f$ or $\lambda$. Both must change at the same time proportionately to maintain a constant speed of light - if wavelength doubles, frequency must halve.
Doppler Shifting makes this apparent - when moving away from a source of waves, the distance between each wave front increases, which reduces frequency, since each wave front takes a bit longer to reach you. Signals who's source was moving away from you at the time of emission will appear to have lower frequency then they ought to by virtue of their source's motion at the time.
Due to Doppler Shifting, if the source galaxy is moving away from us, then the arriving photons appear more 'stretched' then they ought to be - just like sound waves would be (without the simplicity of air to "vibrate in"). They too would have lower frequency from our point of view, and from the galaxy's point of view the photon will always have the same frequency.
This doesn't mean any energy has gone missing. What it does mean is that the energy you measure depends on relative motion, so depending on your choice of reference frame, values for energy (just like for speed and momentum) can change numerically but not physically.
Consider a photon trapped between two perfect aligned mirrors - each 'bounce' would be transferring momentum from one mirror to the other with known energy. If you're flying past the mirrors at relativistic speeds, you would never see the mirrors measure a different force despite seeing the photon taking on a Doppler-Shifted value for energy and always traveling at $c$.
What will complicate this answer is that the universe appears to be expanding. So in fact not only would a distant galaxy be moving away from us, but also appear to be accelerating away from us. This means that for a galaxy emitting a photon, if it could see it somehow, it would notice it slowly Doppler Shifting further into lower frequencies as it gets further from the galaxy.
So to address this directly:
How does a distant galaxy know about the relative speed of a future observer in order to know how to Doppler shift its emitted photons.
It is a bit mind-bending but it is the case that a photon emitted from one galaxy and seen in another, has traveled that entire distance in 'an instant'. As far as the photon is concerned, the emission and absorption (in your eyes for example) happened at the same time, so the relative motions of the source and destination are seen 'at the same time' from the photon's POV.
Though, care has to be taken when talking about the POV of a photon - an inertial reference frame does not exist at light speed but for argument's sake (and some hand-waving) you can think of anything undergoing motion at light speed as 'frozen in time'.
Effectively we're seeing a photon that is carrying a set amount of energy, that was emitted in a reference frame that is moving away from us, and because it's still (in a sense) in a reference frame that is moving away despite traveling all this way, it will be shifted.