If you have a dedicated server, set it up to relay the email to the sendgrid SMTP (configuring postfix or sendmail) and let Newsletter to use the standard delivery method of WP (the wp_mail() function). In this way you move all the sending effort to the server.
Alternatively, try to use our sendgrid addon.