In fact 60V, 34A is well within reach of solid state solutions. You'd need beefy MOSFETs or IGBTs, or maybe solid state relays. You definitely will need opto-isolation between the two with this kind of currents and a good heat sink. Not going to be cheap of course, but for this kind of project that's probably less of a concern.
Indeed PWM output won't go well with relays, it'd kill them very soon. But even at a few seconds on/off periods that'd be a lot of clatter for 15-16 relays.
For your "catching up" problem, another, very basic approach could be to keep track of which one has the lowest temperature, and then when any one heater is more than say 5 °C higher than the lowest, switch that one off until it is no more than 1°C higher than the lowest, then switch it on again (this as it takes a while for the heater to react, so don't wait until it's at the lowest point). That would be a few lines of code to handle. This is basically what your human controls are doing now.
The keeping it at a fixed temperature is more of a PID thing.