Electrolytic capacitors (including tantalum) are polarized. Other capacitor types are not.
Electrolytic capacitors don't "act like" capacitors at high frequencies. In fact, they can become inductive with their impedance increasing at high frequencies.
If a voltage regulator (or other IC) becomes unstable and oscillates, it's usually going to oscillate at a very-high frequency (somewhere in the MHZ range).
So, we need a non-electrolytic capacitor to create a low-impedance "short" for any high-frequencies. You can have an electrolytic in parallel for better filtering at lower frequencies.
Stability/instability is related to the negative feedback which holds the voltage constant under varying conditions. If there's enough phase-shift for that feedback to become positive you get an oscillator. It get's mathematically very complicated and I don't understand it... I think it has something do with [u]Laplace Transforms[/u]. I took a class about it a million years ago, but I never applied it to the real world and I don't remember. But even if you know the math, we don't know enough about the internal physics of the 7805 to make the calculations. And, there's a good chance that whoever developed the 7805 chip doesn't know either... They probably determined that a capacitor was required experimentally...