Firstly, you should be looking at what the voltage is doing with an oscilloscope, on both sides of the regulators, under load. The DC measurement of 19.5V isn't accurate because it's not pure DC. Your multimeter probably does RMS measurements assuming sinusoidal waveforms, which is moot because that's a feature of its AC measurement mode.
Your unregulated power supply's voltage causes too much drop out. Find one that puts out around 15V. You can go as low as 14.5. See this question: 7812 minimum input voltage?
Minimizing the drop-out will knock Watts off the heat production.
The wall-wart may not have enough of a reservoir capacitor inside. Or maybe none at all: just a transformer and bridge.
The 0.33 uF capacitor on the input side of your regulators is almost certainly not enough to sufficiently reduce ripple. Ripple has to be reduced at least to the point that the voltage on the input side never dips below that minimum 14.5V needed for the regulator to maintain regulation.
The 0.33 uF capacitor value from the datasheet is not intended to be a reservoir capacitor. It is not required if you have a reservoir capacitor close to the regulator; it's there for stability and should be designed if the reservoir capacitor is far from the regulator (for instance, if it is inside the unregulated supply).
Putting two and two together, it should be obvious that the reservoir capacitor also helps you minimize the input voltage: the smaller the peak-to-peak ripple you can achieve, the closer the voltage can be to the minimum.