With sound waves, your speed is added to the speed of sound and you hear a different note. With light, the speed remains at c, but perceived energy of the photons is still affected (energy must be preserved after all). And energy ~ wavelength ~ color.
You can also think about it being one of these "zero (weight of a photon at rest) multiplied by infinity (energy of objects moving at c) gives a finite number (actual energy of a photon)". The last number still behaves nicely.
If you imagine an idealized light source, where photons come into existence out of nowhere, then there is no conservation of energy (energy is being created). But in a more realistic model where photons are emitted as a result of electron excitation, say, energy is conserved because the electron recoils when firing off the photon, so the extra observed energy of a blueshifted photon can be found in the extra kinetic energy of the electron as observed in that same frame of reference.