Why does dispersion increase with wavelength? If I understand correctly, refractive index is decreasing with wavelength. As a result, greater wavelengths are traveling faster. How does this cause the increase of dispersion?
It is not true that refractive index is a monotonic function of wavelength. A Google search will quickly show that nearly all materials have increasing refractive index with increasing wavelength in some parts of the spectrum, and decreasing in other parts. What matters is which side of a resonance you're on.
Let's say you have a nice tight wave shape. Now decompose it into sine waves with a Fourier transform. Then let sine waves time-evolve: as you say different frequencies travel at different rates (in a dispersive medium).
When you at the later time add the sine waves back together (with an inverse Fourier transform), the wave packet is not so tight anymore. It has broaden, dispersed.
If all the sine waves traveled at the same speed, there would be no broadening, no dispersion.