I found the problem.
I just completed a lot more testing, trying to narrow down this issue. A couple days ago, I already tried disabling plugins that were "special" or not common, in trying to see if I could find a conflict. I didn't find one. I just did an exhaustive test though, disabling any plugin that isn't a standard Joomla plugin.
Once I disabled any of those, the checkout process was working fine. So I starting enabling them one by one. The plugin that broke the website was a simple one that just inserts Google Analytics code for me. I found an upgrade to the plugin, installed that and found it didn't help.
So I went the manual route and added the standard Google Analytics code the the template files myself. Done that tons of times in the past. Even doing it that way, the checkout still breaks the website.
So I tried disabling the HikaShop Google Analytics plugin. That did the trick. The checkout process works perfect now.
Did you folks change something in the HikaShop Google Analytics plugin? Anything that could be causing this?