As you noted, the regulator can dissipate a large amount of power, depending upon the output voltage and current. It's proportional to the output current and voltage drop across the regulator, thus it is maximum with the output is near 0V, where it would be over 30W at 1A. That's true for any linear regulator, independent of design. Only a switching type regulator will reduce this dissipation.
You need to mount the LM317 on a large heat sink using thermal grease, probably about a 4' or 5" square aluminum sink with fins if you want to output high currents at low voltages. You could also add a small fan to help cool the heat sink.