Caching building coverage
The idea of caching the information which buildings are in range of an effector-building (which you can cache either from the effector or in the affected) is definitely a good idea. Buildings (usually) don't move, so there is little reason to redo these expensive calculations. "What does this building affect" and "what affects this building" is something you only need to check when a building is created or removed.
This is a classic exchange of CPU cycles for memory.
Handling coverage information by region
If it turns out you are using too much memory to keep track of this information, see if you can handle such information by map regions. Divide your map into square regions of n*n tiles. If a region is fully covered by a fire department, all buildings in that region are covered too. So you only need to store coverage information by region, not by individual building. If a region is only partially covered, you need to fall back to handling by-building connections in that region. So the update-function for your buildings would first check "Is the region this building is in covered by a fire department?" and if not "Is this building individually covered by a fire department?". This also speeds up updates, because when a fire department is removed, you no longer need to update the coverage states of 2000 buildings, you only need to update 100 buildings and 25 regions.
Delayed updating
Another optimization you can do is not updating everything immediately and not updating everything at the same time.
Whether or not a building is still connected to the road network isn't something you need to check every single frame (By the way, you might also find some ways to optimize this specifically by looking a bit into graph theory). It would be completely sufficient if buildings only check for that periodically every few seconds after the building was built (AND if there was a change to the road network). The same applies to building range effects. It is perfectly acceptable if a building only checks every few hundred frames "Is at least one of the fire departments which affect me still active?"
So you could have your update-loop only do these expensive calculations for a few hundred buildings at a time for every update. You might want to give preferences to buildings which are currently on the screen, so the players get immediate feedback for their actions.
Regarding Multithreading
City builders tend to be on the more computationally expensive side, especially if you want to allow players to build really large and if you want to have a high simulation complexity. So in the long run it might not be wrong to think about what computations in your game can be handled asynchronous.