I have a work Exchange email account and an iCloud account. On IOS 13.1.3 now, although I experienced the same behavior as on previous release and beta versions of IOS.
Exchange account is working perfectly for me, iCloud hangs on "checking for mail..." most of the time. Occasionally it will resolve after 30 seconds or so, but more than often I have to close the Mail app, wait 20 seconds, then reopen the app for it to (maybe) resolve.
Again, this is only with the iCloud account, so it is not Exchange causing the issue.
Grrrr, come on Apple, these are release versions of your software. They must have changed their policy regarding what is okay to release - if they continue to allow these mail bugs in release versions, they will end up losing their good reputation. Sad.