Mail receivers often track sender spam reputation per IP address. If you use a third-party provider to send the emails, then it is their IP which will take the reputation hit not yours. This is important to understand, as you don't want your all-important company Email Server to be on the same IP that sends a questionable quantity of emails.
Make sure that your email server is properly configured with a correct rDNS entry set up by your ISP. Also you should keep proper SPF records up to date.
You should throttle your emails. Sending them 'as fast as possible' will surely get you banned. It is much safer to spread them out with a delay between emails.
It is likely that your email traffic will have to go up gradually, or perhaps you will have to fill out unblock requests from the big carriers (Microsoft, AT&T, etc) as they will not take kindly to the huge spike in traffic (assuming this IP sends only minimal traffic prior to this)
You can also list an official unsubscribe feature, so that the mail client (i.e. Gmail) can provide a simple Unsubscribe quick link.
If you send enough email from your domain, Gmail will provide you with reporting on how well your emails fair.
There must be some canonical answer to how to properly format emails to avoid spam marks, but I'm not sure where it is.