Default [Q] Galaxy S4 Google + other Issues - memory wipe doesn't help


Please help, this is driving me insane.I've had a galaxy S4 for almost a year now. I had it rooted and ****ed around with it a bit, it was all good. Then I was running low on space and got a disk checker or whatever it's called to show me how my space was being used. A lot of it was in caches. I downloaded a file manager and went on a cache deleting spree. One of the caches I deleted was google. Ever since that day everytime I start my phone:
Samsung Link has stopped
Dropbox has stopped
Google + has stopped
Google search has stopped

The phone in general just worked extremely ****ty.So I decided today that it was time for a factory reset. I run it, all good. The phone restarts in factory settings.. and I get the exact same error messages. ?So I decided that I would do the hard reset. Shut it off, volume up + home + power, wipe/delete all data. EXACT SAME PROBLEM. WHAT?How is that possible? I wipe my phone completely and end up with the same problems? How do I reinstall the OS? Since I'm going to be uninstalling the OS completely (probably the only solution to my problems), is there anyway to get a nice clean OS? And not the one full of bloatware from my carrier? I really just want to start over from a fresh OS.

I also tried just running a software update, but I got the error message 'this phone has been modified and cannot be updated'. I guess that's because it's rooted..

Thank you for your help