Okay, I was able to troubleshoot this over the last few days and I think I finally resolved this.
Here's what I did:
Day 1: did the bloatware cleanup, disabled unwanted services and apps, turned of auth-sync on all accounts etc... I basically applied all the generally recommended fixes
Result...