I have investigated this issue, and on my server (PHP 7.2.16 or PHP 7.3.3 / imagick 3.4.3 / ImageMagick 6.9.4-10 Q16 x86_64) running more or less stock 3.80 with Bender theme (irrelevant), I had only issues with portrait images posted using ImageMagick. As in your heic example, it was captured with iPhone 7, so here is my test:
iPhone 7 / 7 Plus / plus few Android Phones(Safari browser with iOS devices)
GD Library | with PreResize plugin | without PreResize plugin
landscape | no issue | no issue
portrait | no issue | no issue
IM Library | with PreResize plugin | without PreResize plugin
landscape | no issue | no issue
portrait | no issue | YES - ISSUE!
In ALL 4 test cases I have NOT experienced any quality issues you've encountered and described. Problem with autorotation is that it seems both ajax and later processing stages are rotating the image twice, which creates the problem. I am not sure, but that seems to be the most logical scenario according to my tests. Also, not sure how this slipped through before, maybe things changed... I need more samples and tests for this to draw a conclusion. In any case, core code is correct, nothing wrong with it, except this rotation issue.
I already have a fix for rotation problem, will post it later. Initial tests show that it is working.
Test examples from above compiled table are available (for a limited time) on my demo website (url under my profile), just so you can see that I'm telling the truth. You can see that beside rotation issue, quality does not suffer and I don't see any reason to change anything in that regard.
In case if you use preResize plugin by teseo, issue is not present in all cases (GD/IM).
My theory is that your theme uses very small thumbnails instead of larger images, and maybe that creates a problem for you.
Regards
dev101