Is there a reason why you're limiting yourself to evolutionary innovations that occurred after human speciation? Most of our thermoregulation techniques are at least as old as the Triassic, which was much warmer.

Conversely, less elaborate adaptations can happen very quickly. The pale skin of Europeans seems to have originated after the end of the last ice age, for example.

It's also worth pointing out that our species seems to have been basically regional until about 60,000 years ago. So even if we limit ourselves to the last 200,000 years of adaptation, we should calibrate those expectations based on the African regional temperatures rather than a global average. Humans living in New England today may well be experiencing colder temperatures than their ice age ancestors.