Gmail flagging Dovecot email as insecure

I solved this by adding both these lines to Postfix's main.cf:

smtp_tls_security_level = may
smtpd_tls_security_level = may

(I had only set smtpd_tls_security_level because of a misleading article that said all smtp_ values were depreciated in favour of smtpd_.)

Your email is sent unencrypted. If you just want to try your best add the following to your main.cf

smtp_tls_security_level = may

To enforce TLS encryption for email sent to google add this to your main.cf

# Force TLS for outgoing server connection
smtp_tls_policy_maps = hash:/etc/postfix/tls_policy
smtp_tls_CApath = /etc/postfix/rootcas/ 

replace /etc/postfix/rootcas/ with the location of your trusted Root CAs and in the file /etc/postfix/tls_policy add

#/C=US/O=Equifax/OU=Equifax Secure Certificate Authority
gmail.com       secure ciphers=high
google.com      secure ciphers=high
googlemail.com  secure ciphers=high

this will enforce that email sent to gmail.com., google.com and googlemail.com are sent encrypted and authenticating the SMTP server

If you don´t want to authenticate and just encrypt (this is is necessary for sites with bogus certificates) use

gmail.com       encrypt ciphers=high
google.com      encrypt ciphers=high
googlemail.com  encrypt ciphers=high

before restarting postfix execute

postmap /etc/postfix/tls_policy

Consider the client/server relationship with regards to SMTP and the settings make sense:

2.1. Basic Structure

The SMTP design can be pictured as:

              +----------+                +----------+
  +------+    |          |                |          |
  | User |<-->|          |      SMTP      |          |
  +------+    |  Client- |Commands/Replies| Server-  |
  +------+    |   SMTP   |<-------------->|    SMTP  |    +------+
  | File |<-->|          |    and Mail    |          |<-->| File |
  |System|    |          |                |          |    |System|
  +------+    +----------+                +----------+    +------+
               SMTP client                SMTP server

(Src: rfc5321.txt)

Thus:

"smtp_tls_security_level" is for the Postfix SMTP client. See: http://www.postfix.org/postconf.5.html#smtp_tls_security_level

"smtpd_tls_security_level" is for the Postfix SMTP server See: http://www.postfix.org/postconf.5.html#smtpd_tls_security_level

When postfix is transferring mail to gmail, the smtp_tls_security_level setting is the associated setting.

When postfix is receiving mail over smtp, the smtpd_tls_security_level setting is relevant.