To change the port of your outgoing server, see the bottom screenshot on this page:
“Outlook Email Options”
You can get there by going to Tools -> Account Settings. Then select Advanced and then change 25 to 587.
UPDATE: Seems like every ISP (including Verizon FIOS) is now closing port 25!