You're noticing a delay between mailgun getting the email and it getting to the client?
I'm using their REST api to send emails, and I've yet to see an email take more than a couple of seconds to get to destination (gmail) while testing.
How long is too long?