Definitely relays, but NOT a single DPDT one - you need two seperate relays - one to turn on for 110v, the other to turn on for 230V. Plus a short delay between opening one and closing the other.
The reason is that on a changeover relay contact, as the contact opens, an arc can form between the contacts, and may still be burning by the time the common contact hits the other side, so you now have an arc connected right across the mains input.
Break-before-make may well not prevent this at the sort of heater currents you're talking about.
below is a circuit I used to do exactly this job many years ago, using two 115v heaters.
RL1 closes for 230v, or RL2 for 115V
It also includes the voltage detection circuit - the output of optoisolator U2a produces pulses at either 50hz or 100hz depending on the supply voltage.
U3 is for heater-open detection.