If your SMTP server is using SSL on port 25 (via the STARTTLS command), you need to change the TCP port on your iPhone. I was having the same issue with mine, took around 3 minutes to send a single email.
Turns out, my iPhone was trying to connect to some port other than 25, and then timing out after 3 minutes and trying again on port 25. Once it tried port 25, it took only 1 or 2 seconds to send the mail.
Change your server port number in the mail settings section of the settings application. On version 1.0.2 you have to add ":25" to the name of your SMTP server. So if it is "someserver.com" change it to "someserver.com:25". For version 1.1.1 you can change the port number in the advanced settings screen.