Please do a full **clean** re-install:
- move any valued save games elsewhere, and user_empire_designs.txt from /Documents/Paradox Interactive/Stellaris/ if you have made any custom empires or races.
- "uninstall" in Steam-Stellaris
- manually delete both the Steam/SteamApps/common/Stellaris AND Documents/Paradox Interactive/Stellaris folders
- re-install game in Steam, run a Steam Verify when done.
- add stellaris.exe to the exceptions list of your antivirus app; ESPECIALLY if you have Windows Defender, add it to the Ransomware "Apps Allowed Through" list.
- add stellaris.exe to the exceptions list of your firewall app; ESPECIALLY if you have Windows Defender, add it to both the Public and Private domains there
- start the game with no mods active and test
In particular you need to make sure there are no files or folders left under either the Steam Stellaris or Documents Stellaris locations, before installing again.
If nne of that helps, have all players opt into the crossplay branch in the Steam Betas tab for this game, which uses Paradox MP instead of Steam's - any better?