How to limit current for voltage regulator/decrease power dissipation?
Just because a regulator is able to output 5 A of current, does not mean it can do so over it's entire input range - especially not without a good amount of heatsinking (potentially with fan). The reason both of the devices heat up the same is because they have to get rid of the same amount of power, given by 

$$P = (V_{in}-V_{out}) \cdot I$$
which in your case is about \$(12\ V-5\ V)\cdot1.5\ A = 10.5\ W \$, which is a lot of heat! (there is a reason computers have big heat sinks with fans on top).

You have a few options. You can look at going to switch-mode powersupplies, which are far more efficient (because they don't lower the voltage by turning the excess into heat). 
Alternatively, you can look at using multiple regulators in series - Use a regulator to go to 9V, then to 7V, then to 5V. This way, the load is spread out over multiple regulators and each has less power to dissipate (of course the total dissipated power is the same!).
Finally, you can look at using external components like you already were doing. You mentioned having issues - I would suggest trying that topology with lower loads and a good amount of protection on the powersupply end to see what is going on - could be that you are getting some kind of instability.