Was able to reproduce it with an opened terminal
AFAIK the terminal has a tendency to slow everything down... The theme changing is mostly just adding/removing style html tags, so I wonder how much faster this could be made.

People say it is not recommended to call context.fillStyle too frequently, but it is
https://github.com/xtermjs/xterm.js/blob/dd7a9c3b7a7ef060e91b022845f6084d51f29437/src/shared/atlas/CharAtlasGenerator.ts#L75
Although the inner loop variable is not used at all.
Are we still using an Xterm fork? How difficult would it be to try out a few modifications?
There is another minor glitch with this, when the user does Ctrl/Cmd+P > Change Color Theme
Then the currently used theme is set again. It is unnecessary.
Do nothing and close the Command Palette (Esc), then we set again the current theme. I think the logic should be a bit smarter and not set the value if the current theme is the same as we want to set. (Other solutions are good too.)
You should switch to the dynamic char atlas, this should fix this problem for the most part as well as improve perf across the board. This was introduced in v3.4 https://github.com/xtermjs/xterm.js/releases/tag/3.4.0, we're also replacing the static char atlas with it soon https://github.com/xtermjs/xterm.js/issues/1576
@Tyriar thanks for the heads up, we will try
I don't have time to try out https://github.com/theia-ide/theia/issues/2503#issuecomment-440364041, if someone can open a PR with changes it would be very welcomed!
@akosyakov done here: https://github.com/theia-ide/theia/pull/3803