Time and again, I've been told that the change in the velocity of light makes it bend at the interface between two different media. But is there any explanation as to why that change occurs? Or is it one of those things that you just have to accept, like positive charge attracting a negative charge, or something like that?
The velocity of the electromagnetic disturbance changes in different mediums because different mediums / molecules / atoms have different charge configurations and therefore the electromagnetic field has different coupling strengths to the charges: highly polar, long bonds look like dipoles, electrons in different atomic shells are shielded to different degrees owing to their different distances from the atomic nucleusses in question and so forth.
You can think about this a number of ways. Light in a medium is a quantum superposition of true light - that in a vacuum - and excited matter states. If there is only weak coupling with the charges, then the superposition looks almost the same as pure light - the weights of the excited matter states are small in the superposition - and the disturbance's speed is near to $c$. If the coupling is strong, so then is the shift in the superposition's nature away from that of light in a vacuum.
Another, less accurate but evocative and intuitive, way to think about this is Richard Feynman's favorite explanation. One can think of light in a medium as a sequence of absorptions and re-emissions of photons by the matter. In between these events, the light travels at $c$, but the energy "lingers" in temporary absorbers and is thus delayed overall, as I discuss in more detail here. Different arrangements of charge in these absorbers lead to different delays. Different densities of materials also change the probability of and mean time between interactions, thus also changing the overall speed.
However, a much more direct way of understanding refraction of light, in my opinion, is through the continuity boundary conditions for Maxwell's equations / wave equation (it works for sound too). This is not as abstract and as involved as it sounds: see my answer here. A simple diagram illustrating the geometry of this statement leads directly to Snell's law.