I recommend you check out this thread on another site:
http://www.everythingiphone.com/forum/iphone-software/e-mail-issue-3087-2.html
It provides info on AT&T's outgoing servers. The down side is, they will only work via EDGE, not Wi-Fi (unless you're on AT&T Wi-Fi, or a wireless network connected to AT&T broadband).
Another option is to try your ISP-provided SMTP server, using your username and password from the ISP. (Also try with no username and password.)
I currently have this working with the following settings:
Outgoing server: (my ISP's SMTP server)
username and password used
Incoming SSL
Outgoing SSL
This works when I am on my home Wi-Fi (via my ISP), and from EDGE, and should therefore work (and be secure) from any network I am on. This is probably the ideal setup.