I'm running Windows 10, and SOF seems to only play smoothly in windowed mode.

If I run it in fullscreen, the game will periodically (and frequently) freeze in the opening menus.

If I start the tutorial in fullscreen the game will lag really badly.

Any known fix/cause for this?

Try it with SofPlus

https://web.archive.org/web/20180302152559/http://sof1.megalag.org/sofplus/

It adds support for new graphic cards, widescreen support etc.