Why do prisms work (why is refraction frequency dependent)? It is well known that a prism can "split light" by separating different frequencies of light:

Many sources state that the reason this happens is that the index of refraction is different for different frequencies.  This is known as dispersion.
My question is about why dispersion exists.  Is frequency dependence for refraction a property fundamental to all waves?  Is the effect the result of some sort of non-linearity in response by the refracting material to electromagnetic fields?  Are there (theoretically) any materials that have an essentially constant, non-unity index of refraction (at least for the visible spectrum)?
 A: I will hand wave here, looking at the problem a photon at a time.
We know from the double slit experiment that even individual photons impinging on the double slit geometry display an interference pattern, characteristic of the frequency/energy of the photon and the geometry of the slits.
One can think of a crystal as a very large number of three dimensional obstacles/slits ( 10^23 molecules in a mole give a huge number even for a one centimeter crystal in the path of your illustration). 

A photon impinging on the surface of the lattice, finds not two slits , but a depth of slits all the way through. The observed effect of the different angular distribution according to the impinging frequency of the photon must be the result of the quantum mechanical interference of the photon, which must be constructive in the angle of refraction given by its frequency and index of refraction and destructive everywhere else, otherwise we would be seeing interference fringes  ( actually we do get a second rainbow, but that is a different story :) , though should be similar).
Then the problem is reduced to explaining the frequency dependence. I will hand wave again and say that the smaller the frequency the larger the distances in the interference pattern of the probability wave ; the photon will see the lattice gaps differently 

according to its wavelength, as is true for the double slit experiment, so a fanning out is to be expected .
A: Lorentz came with a nice model for light matter interaction that describes dispersion quite effectively. If we assume that an electron oscillates around some equilibrium position and is driven by an external electric field $\mathbf{E}$ (i.e., light), its movement can be described by the equation
$$
m\frac{\mathrm{d}^2\mathbf{x}}{\mathrm{d}t^2}+m\gamma\frac{\mathrm{d}\mathbf{x}}{\mathrm{d}t}+k\mathbf{x} = e\mathbf{E}.
$$
The first and third terms on the LHS describe a classical harmonic oscillator, the second term adds damping, and the RHS gives the driving force.
If we assume that the incoming light is monochromatic, $\mathbf{E} = \mathbf{E}_0e^{-i\omega t}$ and we assume a similar response $\xi$, we get
$$
\xi = \frac{e}{m}\mathbf{E}_0\frac{e^{-i\omega t}}{\Omega^2-\omega^2-i\gamma\omega},
$$
where $\Omega^2 = k/m$.
Now we can play with this a bit, using the fact that for dielectric polarization we have $\mathbf{P} = \epsilon_0\chi\mathbf{E} = Ne\xi$ and for index of refraction we have $n^2 = 1+\chi$ to find out that
$$
n^2 = 1+\frac{Ne^2}{\epsilon_0 m}\frac{\Omega^2-\omega^2+i\gamma\omega}{(\Omega^2-\omega^2)^2+\gamma^2\omega^2}.
$$
Clearly, the refractive index is frequency dependent. Moreover, this dependence comes from the friction in the electron movement; if we assumed that there is no damping of the electron movement, $\gamma = 0$, there would be no frequency dependence.
There is another possible approach to this, using impulse method, that assumes that the dielectric polarization is given by convolution
$$
\mathbf{P}(t) = \epsilon_0\int_{-\infty}^t\chi(t-t')\mathbf{E}(t')\mathrm{d}t'.
$$
Using Fourier transform, we have $\mathbf{P}(\omega) = \epsilon_0\chi(\omega)\mathbf{E}(\omega)$. If the susceptibility $\chi$ is given by a Dirac-$\delta$-function, its Fourier transform is constant and does not depend on frequency. In reality, however, the medium has a finite response time and the susceptibility has a finite width. Therefore, its Fourier transform is not a constant but depends on frequency.
A: 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‎
A: Provided that the electron & the atomic beams also exhibit refraction,it seems that this is a particle's property.Velocity and deflection angle depends on particle's mass/size for specific medium.Photon behaves as particle in this effect.Mass is given by de Broglie equation:m=hv/c^2 , v=frequency 
