Picking a cipher suite for embedded system emails
You can support as many or as few as you like - take a look at RC 5247 for TLS 1.2.  If you are on an embedded system w/o any hardware crypto, you may want to skip the RSA algs that take a long time in favor of the ECDH.  In any case, look for an embedded crypto library that available for your toolchain and cpu vs writing it yourself.  It'll save time as well implementation flaws.

You might try initiating a TLS session with one of these email hosts and see what comes back for the algorithms they support - I suspect it's pretty extensive.  Then you could be sure that the ones you pick will work.  

Wireshark is your friend for this.