Like rnolds81, my Mac was crippled by the issue, and I don't go anywhere near Gmail, or Exchange for that matter. I had the iCloud.com account, plus two IMAP accounts.
For those of you experiencing the issue still, do you have any Mail plug-ins (e.g. Attachment Tamer)? Perhaps one of those is having trouble with a particular message.
I know one thing that helped a lot, but did not solve the issue, was to disable the message preview (Preferences->Viewing - set "List Preview" to "None").
I noticed that when Mail.app was trying to decrypt S/MIME messages from Outlook users, it had some significant trouble, but eventually showed the message. Disabling the preview and only decrypting when I really needed to was a big boost. So maybe the encryption/decryption of certificate validation is the issue?