None of the things seemed to solve it or have a noticeable impact.
I tried to further isolate it (for example disabled many effects widgets and anything that did not sound useful) and it happens even with a single player game (so only local) when game is paused (which should eliminate a bunch of things).
I activated the "Frame Grapher" plugin (hope the plugin is still relevant). What I notice: after starting the game (single player with easy bot) I get between 5 and 10 seconds of "very tall red bars displayed" (which I interpret as much lower than 60fps) followed by 5 to 10 seconds of "very small green bars",
The strangest part is that sometimes after an unknown amount of time, I see only green. Like after 15 minutes (after I built some units, did stuff, etc.).
I did not see anything different in infolog.txt between the two modes.
Any suggestions to further debug this?