YAY! I found the offending App. For me it was the SKYMILES app from Delta. Once I uninstalled that, my problems went away.
BTW, Its true that removing Google Search would have solved it but only because the problem occurs the first time I hit the home button after doing any Google search. But the truth is that it was the SKYMILES app that was causing the problem.
For you it might be a different app but if you want to troubleshoot it, this is what I did. To replicate the problem in the shortest way possible, I would just click on the Google search bar on my home screen, then I would immediately click Home. This would replicate the problem 100% of the time. Then I went though and uninstalled 5-10 apps at a time and then came back and did the same thing until eventually, it stopped doing it. Then I reinstalled the most recent 5-10 apps one at a time, testing in between, until it started up again. It nearly drove me nuts.
Hope that helps someone.