A while ago, I mused on how network latency affects my email usage - one other cause of slowness in my mail client has been GPG key verification. Occasionally, when Evolution wants to check a signature, gpg takes 30 seconds or more to run, and the text of the message is not displayed until the end.
The reason gpg runs so slowly is that it sometimes checks its trust database to make sure it's up to date. However, it does not make sense to run this at the time you are trying to verify an email - it will just slow you down. Fortunately, this is very easy to fix - add 'no-auto-check-trustdb' to gnupg.conf, and set up a nightly cronjob to run 'gpg --batch --check-trustdb'. Ensure that you have 'anacron' installed if your system is not always on.
I have been trying a few methods for solving the network lag problems with email, but haven't reached a conclusion just yet.