Now my only question is, were these two bad components pure coincidence, or did I damage them?

Where did you get them from? Were they previously new/unused?

If they were used, did you have a cap larger than 10uF on the output and short the input? Or have a 10uF or larger cap on the adjustment resistor and short the input?

Maybe my power supply was creating spikes when I powered it on.

Unlikely unless the spikes were above the maximum input to output differential voltage (40V).

I have never zapped any ICs before.

I have never zapped (ESD) any IC's before and I been doing electronics as a hobby for almost 50 years.

I have damaged 3 MOSFETs in the last 5-10 years. 2 2N7000 that were damaged, even though I was trying to handle them correctly and now have high S/D leakage current, and one IRF44N that I connected wrong and fried it.

 

Problem solved -- It WAS bad components! <snip> I rounded up an LM317 in a TO-3 package and it worked correctly. Yesterday my new TO-220s arrived and everything is right with the world again.

Did you remove the regulator that wasn't working and plug the working one into *exactly the same position* on the breadboard? I was just wondering if it could still be a dodgy breadboard connection that you somehow avoided when you put the new regulator in. A dodgy breadboard connection seems more likely than being unlucky enough to have two dead regulators.
Have you checked that it reverts to not working if you replace the working regulator with one of the previously not working regulators?

 

Speaking of breadboards. They're designed for #22 wire (0.025" diameter) and maximum lead diameter supported is 0.032"). TO-220 leads are too wide (up to 0.037"). If you rotate the leads 90 degrees, you won't be abusing the spring contacts. That's particularly important for the cheap ones that use the cheapest type of spring.