If your regulators are expected to run hot, it is either due to large voltage difference or large output current, or both.
A two-stage cascade regulator often works well to reduce the load across a single 78xx or LM3x7. These are reasonably durable devices and can handle 400-500mW continuous dissipation without any heatsink at all, in ambient temperatures of 50 degrees or so. This works out to a current draw of 150mA at 3V drop, which is the minimum for decent regulation.
If you need more current, a TO-220 unit is probably not the best choice without some form of external help or a heatsink. If your voltage headroom is higher, consider a pre-regulator. I've used series resistors when the load is predictable and constant to serve this need, but a second chip really improves PSRR.
I've also used ripple eaters (either series or shunt) close to the load and 3-terminal devices near the power supply when the DC voltage regulation is less of a consideration than noise levels. There are quite a few ways to skin this cat.