My gut instinct is that Excel is having to rerun your calculations on every row. A single calculation that takes 100ms to run is fast. But if you have to rerun that calculation 1000s of times then it adds up quickly. Excel normally only has to rerun formulas that are impacted by a data change you make (e.g. changing a cell value). But if you do something that causes Excel to have to recalculate everything then it'll cause problems.
You mentioned that the spreadsheet is huge. If you're talking 1000s or 10,000s of rows then that is going to get expensive quick. Adding a column is probably forcing the formulas to recalculate (because the relative offsets have changed, perhaps). I'd be curious to know if adding the column to the end of the rows still slows things down.
Removing a column is no different than adding a column so a refresh is still going to be needed. Perhaps you can test this by removing a column that isn't being used in the formulas. See if it takes forever to refresh.
To test this theory you can temporarily disable the recalculation in Excel. In the ribbon bar go to the Formulas
tab. Then on the right side find Calculation Options
. It is set to Automatic by default. Change it to Manual and then add the column. Once you've added it then try reenabling the auto calculation. If it grinds to a halt again then this is the problem.