Mountains
As others have noted, cooling 250 C is quite feasible using existing technology. After all, scientists quite regularly cool experiments to near absolute zero, which is more than 270 C below (water) freezing. Most MRI machines use liquid helium* cooled superconducting magnets and can operate essentially 24/7 in a hospital environment. Note that the insulation required to maintain this temperature is not absurdly bulky, as Peter observes.
Even so, I would suggest that your inhabitants, rather than digging underground, instead burrow into mountains. There are several advantages. First, the mountain provides a large natural thermal barrier, reducing the amount of insulation required for human structures. Second, we already have a ton of tools and experience digging into mountains. And third, the coldest heat sink accessible in such an environment is most likely going to be high-elevation atmosphere.
Solar Chimney
So, your inhabitants will most likely want to build a mega-project somewhat like a massive solar chimney at the top of the nearest/highest mountain. The chimney should be as large as they can afford to construct it, both in terms of height and cross-section. Unlike a traditional chimney, they actually want bidirectional flow, so I would suggest a coaxial design where an inner pipe moves cold air from the top downwards, and the outer section moves exhaust heat upwards.
The theory here is that exhaust heat will be hotter than cold intake heat, and so you want that in the jacket layer, closer to the hot outside air. You want to protect your cold intake air as much as possible. Note that "cold" is relative, and may still be 100+ C at the altitude they can build it.
The top of the chimney should be forked, so that hot exhaust gas can be blown downwind of the cold air intake, and the exhaust vent needs to be able to rotate in response to prevailing winds.
Being able to dump waste heat into air which is 100 C colder than ambient will be a significant energy savings.
Even if your inhabitants cannot afford to build a tall chimney, they can still use the mountain itself as a chimney, either with a rotating external vent, or with multiple vents built into all sides of the summit, and an internal mechanism which can rotate to vent/intake from different ports. But if they have multiple thorium reactors to power their civilization, then they have the tech and resources to build a pretty big chimney.
Ocean
The bigger problem, IMO is water. You haven't said how long the atmosphere has been 500 C, but eventually, you will boil away the oceans. Until then, you could use the deep sea as a heat sink, if you don't mind accelerating the loss of water. Most likely, the thermal output of your remaining civilization will be a drop in the bucket compared to the atmospheric thermal load.
But the lack of rain means that your civilization will have just as much problem keeping water as it does staying cool. Fortunately, the boiled oceans will mostly stay in the atmosphere, making the air completely saturated with water vapor (and probably quite unpleasant to breathe, as it will be super-heated vapor which likely burns your lungs). However, this also gives you a source of water, since you can just take in outside air at whatever elevation has high vapor pressure, and condense the water out of it. Basically, make your own rain.
Good luck!
* Helium boils at 4 K