I am using Gmail email app on android, we have our own corporate email on exchange server.
It is set to push, unfortunately the things you mentioned I have tried them all already, no battery optimization, background data off etc.
It is actually a very known issue and existed in note 8 as well, I returned my note 8 on 3rd day because of this. If you search on internet you will see a lot of threads talking about this issue, I don't know why Samsung or Google is not addressing such a crucial issue.
I mean a 130K phone is not able to pull emails properly specially note series which they advertise more as a business phone is very unfortunate.
On the other hand on iPhone I don't have to worry about this at all, it notifies me about emails instantly, I don't like iPhone X form factor, the notch, it's restriction for customizations, but iPhone is so reliable for my work compared to Android that I have to stick with it, even my work related VOIP calls on hangouts are better on iPhone, slack notifications which is another app that I use for work are also more reliable on iPhone.
You can hate iPhone all you want you can critise there pricing policy but unfortunately there is no other better option than Apple in the market right now for business users and believe me people in Apple knows that.