Thanks a lot!
As usual I spend hours trying to fix it, then decide to post - and 20mins later I sort it out myself.
Turns out the issue was moving characters using physics in Update() as opposed to not using physics or physics in FixedUpdate().
Sorry for wasting your time and thank you for the great break down of problem solving regarding this issue.