Autodiscover worked well for the Outlook clients, but not for the phones. For our Android phones we removed the existing account and readded the account. My Galaxy S4 did not do failover in autodiscover properly from our on-premises autodiscover to Office 365 autodiscover. So, I ended up manually configuring the ActiveSync account.
If you are manually configuring the ActiveSync account for Office 365, the server name is: