Did you try putting it in safe mode, had same issues, lots of lag, goog search very slow and at times not responding, slow loading web pages.. put in safe mode and unbelievable, as fast as first day I got it, goog search came right up, web page right up, everything loaded quickly. Finally after clearing cache, FDR which neither helped as I was reloading the same prob 3rd party app or widget, so did the safe mode to see the issue for me was not the phone, issue finding which app. The biggest problem for me so far was handscent, uninstalling it helped a lot, still going thru other apps as I have quite a few. Trying go SMS now which is posing no problems... Give safe mode a try to see if phone performance greatly improves like my maxx.
BTW... got the new nexus 7 tablet, wow amazing screen and speed, hardly using my maxx now except for calls, mail, texts, navigation and occassional searches... Hope my next phone is this slick, maybe new nexus 5 in Nov.