Ok, first base
B. Diddy's suggestion is a good call. The Play services is kind of a supermanager for most Gapps. If you don't have the latest version there's an easy way to force the update. Go to the Play Store and download Android wear. Once installed the Play Services will be updated in a little while. You can uninstall the wear app after GPS are updated.
And back to our list. Have you transferred any app to your SD card? Try to check in your computer if there's any corrupted file in that card.
I didn't understand a couple of things. You managed to get Google+ working, but is it still working after you exit safe mode? Do you still have the same lag after removing your Google account and adding it back?
That lag means that there's a problem with your accounts or a weird conflict with some app or something wrong with your rom, as B. Diddy said.
Check all your accounts (no Google included). Do you have any battery saver, ram booster, app killer, antivirus or any app with a name beginning with smart? You'd be amazed how many problems in this forum are fixed after you disable that kind of apps.