Got another error after posting this question which led me to the answer:
Handshake failed due to an unexpected packet format
The solution is to connect to Office 365 like this instead:
smtpClient.Connect("smtp.office365.com", 587, SecureSocketOptions.StartTls);