Exchange 2003 is not supported by Outlook 2013. Outlook 2013 does not support many legacy public folder functions, such as the Free/Busy service. Direct booking of calendar resources is also no longer supported.
While this is disappointing to a number of people still using Exchange 2003, it didn't come as much of a surprise. Even ignoring the fact that Exchange 2003 is 10 years old and long out of support, the precedent was set many years ago: Outlook 2010 doesn't work with Exchange 2000 and Outlook 2007 doesn't work with Exchange 5.5. Outlook 2016 probably won't work with Exchange 2007.
Outlook 2013 supports Exchange ActiveSync and while you can use EAS with Hotmail accounts, it won't work with Exchange 2003's (or Gmail's) implementation of EAS. You are limited to POP3 or IMAP with Exchange 2003.
If you want to try Outlook 2013, you can use it with a Hotmail account, Office 365, POP3, or IMAP account if you don't have access to an Exchange 2007, 2010, or 2013 server.
The Office 2013 / Office 365 trial includes an Exchange server account and Office 365 supports "connected accounts". As long as you can use POP3 or IMAP to collect your Exchange 2003 email, you can pull it into the Office 365 mailbox. When you use a connected account, you can reply using the correct email account.
After hearing that Exchange 2003 is not supported by Outlook 2013, one user had this to say:
"What?! My Android works fine with Exchange 2003 but Outlook 2013 doesn't?"
Android, like iPhones, use Exchange Active Sync to access your Exchange mailbox. EAS gives you the basic features of email, calendaring, contacts. Outlook uses Extended MAPI and takes full advantage of everything Exchange Server has to offer. While Outlook 2013 also supports EAS accounts, it requires the full-featured version of EAS found in Exchange 2010, not the older EAS found in Exchange 2003.
Note that Outlook 2013 does not support connecting to an Exchange server using EAS. This is by design for a number of reasons: it results in a degraded experience and can negatively affect performance of the Exchange server.
To get an idea of what your phone supports and what EAS provides, see Comparison of Exchange ActiveSync clients. (Wikipedia)