It is not supposed to be a sine wave, but that's what you get when there is power line noise getting into the system. What you should see is more like this
How to get rid of it is sort of a mystery, because the frequency is too low for hardware filtering to be effective. Trying different outlets can help here in the US since our outlets are mostly not GFCI protected and that seems to be the kind that produce the most issues. Most outlets in the EU/UK are protected by some means (RCD / GFCI / arc fault?) so you might have a harder time with it. I'm not sure how it gets in or how to get rid of it unfortunately.
I'd say your latest image is in the unusable territory considering over the course of 20ms the temperature has varied by roughly 4C which is more than HeaterMeter can deal with even after software filtering.
I had a thought. Audiophiles tend to use some sort of EMI/noise smoothing on the AC input to audio equipment.
Would something like this work for probe noise? - supressing noise before it hits the ac/dc converter.
Maybe? I'm really not sure where it comes from to begin with. I can reproduce it in my kitchen if the probe sheath touches the metal of my toaster oven despite my probe being isolated (no continuity from the sheath to either of the thermocouple pins). That system works perfectly with no noise at all out at the grill or if the sheath isn't touching the toaster. How to get rid of it is just a giant mystery to me.