The simple explanation given in Hewitt's Conceptual Physics is that atoms in condensed matter have a high-frequency resonance, and the index of refraction for most substances is strongest at the blue end of the spectrum because that's the high-freqency end, which is closest to the resonance. The following is my attempt to flesh this out with a little more serious physics. It seems to capture some of the truth, but in some ways it's crude or wrong.
Kitamura 2007 gives a summary of experimental data for silica glass over a wide range of wavelengths, along with a physical interpretation. The graph above is redrawn from Kitamura. What is observed is that the complex index of refraction has three prominent resonances with a shape that I think is referred to as a Lorentzian. At each resonance, the real part of $n$ swings low and then high, while the imaginary part has a peak, indicating absorption. They attribute each of these resonances to one or more qualitatively different physical phenomena. The visible spectrum lies between resonances at about 0.1 $\mu$m and 9 $\mu$m. The former is attributed to "interaction with electrons, absorption by impurities, and the presence of OH groups and point defects," the latter to "asymmetric stretching vibration of Si-O-Si bridges."
Although this is all pretty complicated, I think there's some fairly simple physics that can be extracted.
In the visible region, it looks like the decrease of the index of refraction with wavelength is due to a combination of two effects. This region of the graph picks up a negative slope from the 0.1 $\mu$m resonance on its left, and also a negative slope from the 9 $\mu$m on the right. This is a universal feature of any function formed by adding up a bunch of narrow Lorentzian resonances: far from resonances, it always has a negative slope. The bigger contribution to the slope seems to come from the resonance on the left, which is consistent with Hewitt's explanation.
Kitamura mentions several models that explain the resonances, of which the only one I'm familiar with is called the Lorentz model. In the Lorentz model, you take an electron to be a harmonic oscillator, like a little mass bound by a spring to a nucleus. The displacement of this driven harmonic oscillator (represented as a complex number to include its phase) is the Lorentzian $x=Af(\omega)$, where $f(\omega)= (\omega^2+i\gamma \omega-\omega_0^2)^{-1}$ and $A=(e/m)E$. As the electrons perform this oscillation in response to a plane wave, they generate their own coherenet plane wave. What is actually observed is the superposition of this wave with the incident wave. This superposition has two parts, a reflected wave and a transmitted one. In the limit of a low-density medium (such as a gas), the index of refraction is given by $n^2=1-\omega_p^2 f(\omega)$, where $\omega_p$, called the plasma frequency, is given by $\omega_p^2=Ne^2/m\epsilon_0$, where $N$ is the number density of electrons. The plasma frequency has an $e/m$ in it from the amplitude of the driven harmonic oscillator, and another factor of $e$ because the amplitude of the reemitted wave is proportional to the amount of charge oscillating. In the case of silica glass, I think the 0.1 $\mu$m resonance is probably what is described by the above mechanism, while the other resonances are similar mathematically but involve other effects than oscillation of bound electrons. E.g., the Si-O-Si bridges would resonate at a lower frequency due to the greater inertia of the nuclei compared to electrons.
An interesting feature of the graph is that there are broad plateaus, and as we go up in wavelength, each plateau is successively higher than the preceding one. This is explained by the Lorentz theory. In the limit the response of a driven harmonic oscillator approaches zero in the limit $\omega\gg\omega_0$, but approaches a constant (with reversed phase) for $\omega\ll\omega_0$. Adding the contributions from the various resonances produces an ascending staircase as observed.
Is frequency dependence for refraction a property fundamental to all waves?
The above does seem to suggest that there's some very universal behavior going on in the interaction of EM waves with matter.
Is the effect the result of some sort of non-linearity in response by the refracting material to electromagnetic fields?
No, I think it's basically the linear response of a driven harmonic oscillator.
Are there (theoretically) any materials that have an essentially constant, non-unity index of refraction (at least for the visible spectrum)?
I'm sure this would be a holy grail for people doing optics. AFAIK, the best way of getting rid of dispersion in real devices seems to be combining two materials so that the dispersion cancels out. Silica glass does seem to have a relatively constant $n$, and this would be because the visible spectrum is relatively far from the two nearby resonances. To get less dispersion in the visible spectrum, I guess you would want a substance in which the resonant frequency that glass has at 0.1 $\mu$m was displaced higher.
Kitamura, http://www.seas.ucla.edu/~pilon/Publications/AO2007-1.pdf
