Anya, we recently investigated this same issue with "transactional" emails.
The SFDC/MKTO sync happens 5 minutes after the last sync. Depending on how much info you're syncing between the two, the sync itself might actually take 5-30 minutes (for us).
So sometimes, you're looking at a 30-40 minute delay from when the lead is created in SFDC to the MKTO email hitting the lead's inbox.
MKTO is unable to adjust the 5 minute gap between syncs due to a technical reason. I don't think it'd help much anyway since the bulk of the lag is the sync itself.
The sync cycle can be reduced if you lighten up the sync load.
Another option is to consider syncing the lead to MKTO first and let MKTO handle the push to SFDC.
Yet another option is to use SFDC's email engine to send the initial email if you can stomach the limited features.
We chose to use a 3rd party system (MailChimp) for emails that needed to go out instantly from SFDC.