See
There's PWM and there's PWM. To effectively PWM a driver you need to switch it slower than the time constant of your plant. In this case your plant's time constant is measured in minutes, if not 10's of minutes, so having a PWM period of a minute (or two, or five) is no problem at all. The two biggest concerns that you should have if you choose to PWM are wear on the relay (which you could fix with a solid state relay) and any efficiency lost in the cooling process when the heater is heating up but not yet making the cooler percolate.
If you use my suggestion of switch then wait a while you will be guaranteed switching times that are no shorter than the wait, and will probably be longer because the temperature will change.
1LSB accurate or repeatable?
You may get better resolution (_not_ accuracy) by measuring significantly faster and averaging. Averaging over a power of two interval is easy, because you just add up the readings and right shift the result. If the last ADC bit is really random you'll pick up quite a bit of resolution this way.
I'd suggest 32 times a second -- take 16 samples, add them up. Don't shift them down for internal use -- use the extra 4 bits of noisy data for the resolution they'll give you. Do shift them down for temperature display, however.