Having the same problem since the new security settings. Using Windows 10 Home Edition and Outlook 2016. Set all the right port parameters. Incoming mail works fine (always has) but the outgoing mail just keeps giving me this message:
Your server does not support the connection encryption type you have specified. Try changing the encryption method. Contact your mail server administrator or Internet service provider (ISP) for additional assistance.
The pop-up asking for username and password also comes up whenever there is outgoing mail that needs to be sent.
I selected Port 465 SSL for Outgoing mail.
This is extremely frustrating having to login to webmail to send messages.