Made the problem a little easier to fix for you guys:
I'm running Windows 10 Pro x64, didn't need to set any compatibility flags (can use force 640x480 for fullscreen though)
Step 1: Run game
Step 2: Open Taskmanager, find the game's executable named "KoDP.exe"
Step 3: Right click on game and press "Analyze Wait Chain"
Step 4: Underneath the game's exe you'll find program(s) that are causing KoDP.exe to stall before launching.
Step 5: Checkmark the box under the game's exe and hit end process
Step 6: Repeat steps 3-5 until the game boots up.
Images showing steps 3-5
i.imgur.com/BtJQcUq.png i.imgur.com/O70wG8u.png Makes finding the programs this game hates much easier than trial and error.
More me, it was SearchUI.exe, Skype.exe, and Cortanna.