FYI Ubuntu is the only supported Linux distro for our games. So let's look at the Windows issue.
We can't help with modded games here, so disable them all while we work on this.
Right-click on stellaris.exe, properties, compatibility. Tick "disable fullscreen optimizations" untick every other box in that dialog, Apply, and exit.
Then in the launcher Game Settings menu, select the fullScreen display mode, Vsync off, refresh rate 60.
Now test with a new unmodded galaxy.
If that doesn't help:
DXDIAG is a program you run from the Windows search box on the task bar. After running it will open a window and start collecting info with a progress bar in the lower-left corner. When it completes click the 'save all information' button and save it to a file then attach that file here.
Please attach here your Documents/Paradox Interactive/Stellaris/settings.txt and pdx_settings.txt .
From your Documents/Paradox Interactive/Stellaris/logs/ folder, attach here system.log , error.log , exceptions.log