So here's how it looks like with different programs:
VLC - video doesn't seem to stutter, audio stutters (stops momentarily about 2 times per second). Computer restart can solve that sometimes.
W10 Movies and TV app - video freezes for about 1-10 seconds few times in a minute AND audio doesn't stutter at all.
Windows Media Player (which can be found in W10 also) - no problems at all!

I'm forcefully updated to Windows 10 Pro from Windows 7 Pro SP1 on the launch day and used the "don't leave anything" option when doing the update. Which isn't exactly "clean install" but it did feel so in the end. The Windows also automatically found all the video and audio drivers. My wife used the simple update option with her laptop (didn't wipe anything) and all works well on her computer (also with the new Movies and TV app). My computer specs (which are higher but older than hers) should be in my profile.

I'm guessing there's something to do with either the video or audio drivers or codecs. What could be wrong? Where to begin?