The front velocity, defined as the propagation speed of the point where the field first differs (by any arbitrarily small amount) from exactly zero, is always no greater than $c$. (In fact, the front velocity is always exactly equal to $c$, no greater or less.)
The problem here is that a Gaussian pulse extends infinitely in both directions, so it simply does not have a "front" to speak of. Of course the amplitude decays super-exponentially on both sides, but that doesn't matter. There is no causality problem with the pulse emerging arbitrarily early in time, because your input pulse made the field start changing long before that.
As a thought experiment, let's imagine we have a button we can push to start the input pulse going. If any trace of the output pulse comes out before a signal at $c$ has a chance to propagate from when and where the button was pushed, that's a causality violation. But that is impossible, for the following reason:
Since a theoretically perfect Gaussian pulse has no finite start time, but has a nonzero amplitude at arbitrarily early times, it's impossible to create such a perfect Gaussian pulse by pushing a button. Of course, you can get arbitrarily close to perfection, but there will always be some distortion that gets worse and worse as you try to make the pulse fire "faster", that is, try to make a shorter separation in time between the button push and the maximum of the pulse. The theorem that the medium has a causal response to the field guarantees that the response to this distortion will always interfere with the response to the perfect Gaussian to cancel out exactly at times earlier than a signal traveling at $c$.
Of course, in a real experiment, the "button push" (actually some electronic signal to the machine that creates the pulse) happens a relatively long time before any trace of the output pulse is detected.
Here's a great book chapter I just found about this: http://books.google.com/books?id=kE8OUCvt7ecC&pg=PA26 It has lots more math than my answer (though not too high a level) and might clear up a lot of things.
You also ask about single photons, but that opens up a huge can of worms I can't really get into (not least because I don't understand it well enough myself). Let me just say that there is always a minimum amount of noise in any mode / degree of freedom of the electromagnetic field, which is equivalent to half a photon. You could make a pulse of the right shape that's so weak there's only a single photon in it (I'm sure people do things like that all the time), but the problem is if you try to "announce" too early that you've detected that photon, you'll be wrong such a large fraction of the time that you can show statistically that no information is being transmitted. It's really difficult to do quantum-limited measurement in the first place (because you have to severely limit the back-reaction of the measurement apparatus on the field you're measuring), and if you try to do it too fast it becomes literally impossible.
(This is an intuitive explanation on my part, it may or may not be correct)
Symbols used: $\lambda$ is wavelength, $\nu$ is frequency, $c,v$ are speeds of light in vacuum and in the medium.
Alright. First, we can look at just frequency and determine if frequency should change on passing through a medium.
Frequency can't change
Now, let's take a glass-air interface and pass light through it. (In SI units) In one second, $\nu$ "crest"s will pass through the interface. Now, a crest cannot be distroyed except via interference, so that many crests must exit. Remember, a crest is a zone of maximum amplitude. Since amplitude is related to energy, when there is max amplitude going in, there is max amplitude going out, though the two maxima need not have the same value.
Also, we can directly say that, to conserve energy (which is dependent solely on frequency), the frequency must remain constant.
Speed can change
There doesn't seem to be any reason for the speed to change, as long as the energy associated with unit length of the wave decreases. It's like having a wide pipe with water flowing through it. The speed is slow, but there is a lot of mass being carried through the pipe. If we constrict the pipe, we get a jet of fast water. Here, there is less mass per unit length, but the speed is higher, so the net rate of transfer of mass is the same.
In this case, since $\lambda\nu=v$, and $\nu$ is constant, change of speed requires change of wavelength. This is analogous to the pipe, where increase of speed required decrease of cross-section (alternatively mass per unit length)
Why does it have to change?
Alright. Now we have established that speed can change, lets look at why. Now, an EM wave(like light), carries alternating electric and magnetic fields with it. 
Here's an animation. Now, in any medium, the electric and magnetic fields are altered due to interaction with the medium. Basically, the permittivities/permeabilities change. This means that the light wave is altered in some manner. Since we can't alter frequency, the only thing left is speed/wavelength (and amplitude, but that's not it as we shall see)
Using the relation between light and permittivity/permeability ($\mu_0\varepsilon_0=1/c^2$ and $\mu\varepsilon=1/v^2$), and $\mu=\mu_r\mu_0,\varepsilon=\varepsilon_r\varepsilon_0, n=c/v$ (n is refractive index), we get $n=\sqrt{\mu_r\epsilon_r}$, which explicitly states the relationship between electromagnetic properties of a material and its RI.
Basically, the relation $\mu\varepsilon=1/v^2$ guarantees that the speed of light must change as it passes through a medium, and we get the change in wavelength as a consequence of this.
Best Answer
You raise several points, I'll try to discuss them one by one:
Why does the wave front remain a line? Actually the wave front is a two-dimensional surface not a line, but that's beside the point. The answer to this question is, that we assume a uniform material and a clean, even boundary on a scale large compared to the wavelength of the incident light and a large even wavefront. (Otherwise the law of refraction won't hold – you would have strong diffraction effects and be in a regime where ray optics don't work).
This in turn means, that there is the same field configuration and material configuration at each surface point, so by symmetry the wave front remains a straight line. (You can argue with the Huygens principle here).
If the intensity of the light is high and not entirely uniform over the wave front and the material has the right kind of non-linearity (changing the effective index of refraction with intensity) this may not hold in reality. Then there are lensing effects, where the wave fronts bend around local intensity maxima.
Assumption that speed and wavelength are multiplied by the same factor There is the basic relationship $c = \lambda f$ for the phase velocity of a wave (which comes from the observation, that within one period of the wave, the wave front must advance by one wave length by the very definition of the quantities). So for the the wave length and phase velocity to change by a different factor the frequency of the wave would have to change. This can't happen (up to non-linear effects which may induce higher harmonics of the base frequency), because the wave in the medium is excited by the incident wave, so the excitation there has the same frequency of the incoming wave.
Single photons A single photon does not have a definite path. Depending on the view you take, it either has an extended state functional, or (taking the Feynman integral construction for the propagator seriously) follows all possible paths at once. When measuring the is a probability distribution for the location of the photon, and its maximum is around the "classical path" taken by the rays a corresponding classical wave (because the contributions close to this path add their probability amplitudes are in phase and add up, while those from the non-classical paths cancel out). This is nicely described in Feynman's laymen introduction "QED: The strange theory of light and matter". Feynman also derives Snell's law using these arguments.
Light focussed to a single point This can't work on many levels. You can't focus light to a single point. At first there are practical problems due to the diffraction limit. Also, ray optics breaks down in such situations – so Snell's law can't be expected to hold – as it propagates such a collimated beam would diverge in all directions even in free space. There are also other limits: If you collimate the light more and more, the intensity of the light gets higher and higher – at some point your material will get non-linear and with even more intensity you will just ionize and destroy your material instead of observing refraction.
The bottom line is, that Snell's law is an approximation that holds very well in the geometry optics limit (that is, when your wave fronts are large compared to the wave length). You can derive it easily in the wave front picture under such circumstances. Your thought experiments don't get around this and at most will show the limits of validity of ray optics.