Here is the answer that fixed my sending issues:
Outgoing (SMTP) Server: smtpout.secureserver.net
Port: 465
Use secure connection is checked
Use secure password (TLS): Auto
Authentication: Auto
Verify Certificate is NOT checked
However, now I had folder issues with IMAP. Blech!
So I finally gave in and switched to K9. It all works there, without all this hassle. Too bad the default software built into the phone does not share the same robustness.
Blame Motorola for that one. The stock email client works just fine. This Blur'd up mess they created is in need of a rethink.