SMTP allows unecrypted communication over port 25. For some servers (like Google's MX servers) I'm able to switch to a TLS connection using STARTTLS after making the initial unencrypted connection.
S:220 mx.google.com ESMTP l1si352658een.133
C:EHLO mail.example.com
S:250-mx.google.com at your service
S:250-SIZE 35882577
S:250-8BITMIME
S:250-STARTTLS
S:250-ENHANCEDSTATUSCODES
S:250 PIPELINING
C:STARTTLS
S:220 2.0.0 Ready to start TLS
[socket switches to TLS here]
C:EHLO mail.example.com
...
However, I would also like to support straight SSL connections and I'm wondering whether most mail servers prefer starting with SSL or starting with TCP and then moving to TLS after a connection is made.
Unless you have prior arrangements with the administrator of a sever, don't try to connect using SSL. Port (465) was used for SSMTP or SMTPS (SMTP over SSL). Connections to this port were expected to start the connecton with SSL. Use of this port and protocol has been abandoned now that StartTLS is available.
There are two ports which may support SMTP with StartTLS. Neither are expected to support SSL without StartTLS, and will likely drop the connection if you try. Both the SMTP (25) and Submission (587) may support StartTLS. If it is supported, it wlll be listed in the response to an EHLO message. You can then initiate the StartTLS process. See RFC 3207 for more details.
It appears from your comments, that your real concern is how to verify the certificate. That is a different but related question. It also assumes that mail servers are not using self-signed certificates. In my case, I use a self-signed certificate. This works well for me as StartTLS is rarely, if ever, used for SMTP (port 25) connections. I have reasonable control over the clients connecting for message Submission (port 587 or port 25) that must authenticate before sending messages. In my experience, StartTLS is mainly used to secure the connection for clients that must authenticate before sending email.