EDIT: 3 posts before I finished writing! I'm slow today

Datasheet max limit numbers are all independent requirements; ie the 500mA should be treated only as a max current limit, not a thermal limit. For example the chip also claims a max voltage of 35V, but it has zero chance of doing that at the same time as 500mA (*= 18W) continuously.
3W from an IC into a 2-layer PCB, assuming you have no forced air or other heatsinking, does seem like a bit much.
If the outside of the D2PAK is 85degC and the thermal resistance between the junction (silicon) and case (metal tab) is 5degC/W then the silicon die is probably about 100degC. That's well within the chip's 150degC limit. Alas, you might be measuring the temperature of the plastic bit of the case, not the metal tab? And you only did a short term test?
Sidenote:Thermal cameras are awful at reading small reflective metal surfaces like IC metal tabs, you will probably want to use something like a small thermocouple taped on.
You could take some of your 3W away from the regulator IC and share it with some large series (24V-side) resistors. They can handle high temperatures well. The system will still dissipate the same 3W total, but a smaller fraction of it will be in the regulator IC. Make sure to calculate their resistances assuming a highest-worst-case current draw so that the regulator will still see its minimum acceptable voltage (usually the input voltage needs to be a few volts above the output voltage for regulation to work reliably, check the datasheet).
I would always encourage trying some buck converters. On this note, please don't use a 34063, it is a very old design that requires bigger parts and has far fewer protections than is considered normal these days (it blows up violently if you make a mistake). There are lots of 6-pin buck regulators (usually SOT23-6) out there that need nothing more than some resistors, capacitors and one inductor to work. Eg the DIODES AP63/64 series parts
like this one, or a
TI TPS part. I found these parts by sorting by highest stock levels, but there are also dedicated online tools like
TI WEBBENCH.