I had this same problem on a Sprint Galaxy S4. Finally figured out that when I "deleted" emails, they were really sent to a "Trash" folder (not truly deleted). Every time I opened the email app, it had to load the thousands of "Trash" emails. As soon as I emptied the Trash folder, my email opened immediately every time. This was never a problem with KitKat. Hope this helps