LM2596 buck converter overheats converting 36DC -> 5DC at 600mA
These converters are often advertised on eBay as working up to 40V and 3A with 92% efficiency. Don't believe it. 

The 'LM2596' may be a fake. But even if it's a 'good' fake, what kind of performance can you expect? I simulated the LM2596 in TI's WEBENCH®. Here's the circuit...



And here's the simulation result...



Only 74% efficiency at 600mA! That equates to 1W of power loss, which could make a small board quite hot. However in the simulation the inductor only dissipated 0.16W, much less than the LM2596's 0.54W. Your inductor is getting hotter than the IC, which suggests it may have higher resistance and/or magnetic core loss than the simulated component.   

The combination of low inductance, high voltage drop and low current results in high ripple. A circuit designed for low output current might achieve higher efficiency by using a larger inductance value, but then it would be worse at high current. I am guessing the original designers of this converter wanted to get the greatest current and voltage range they could out of it, so they used the minimum inductance value they could get away with. Then someone else copied the circuit, but substituted the inductor for a physically smaller part with higher resistance and lower saturation current. And if the LM2596 is a fake...


  Is it reasonable to chain the converters, like using the first buck to
  drop something like 36 -> 20, and then the next one to drop 20 -> 5?


Yes, this should help. Efficiency improves at lower voltage drop, so you could try cascading converters (eg. first from 36V down to 12V, then from 12V to 5V) so the voltage differential that each one has to handle is reduced. Total efficiency may be worse, but each individual converter is more efficient so they should run cooler.