Try a PC anyway?
I have had the exact same problem. (Note that I have never rooted my phone, etc.)
I decided to try Samsung support live chat. After walking the support person twice through the experience, and a soft reboot once, I got the following:
" I request you to connect your device on PC and check if you can upgrade."
About to grab my work computer (a PC) and see if it does any better than my Mac. Will post again if it solves the problem.