Well, that was easier to fix than it seemed…
A ton of my old comments were sorted apparently randomly. It took a little digging, but I finally discovered that at some point, WordPress added a comment_date_gmt field in wp_comments, and during some import most comment dates had been initialized to the default (’0000-00-00 00:00:00′). The comment query sorted by this field with identical values for every comment, so the resulting order appeared random (it was actually sorted by the comment_id, which was not chronologically ordered due to various imports in the past).
Anyhow, I added 8 hours to the comment_date to get to the normal PST/MDT time and fixed this nicely:
UPDATE wp_comments
SET comment_date_gmt = comment_date + INTERVAL 8 HOUR
WHERE comment_date_gmt = '0000-00-00 00:00:00'
If anyone finds this, run a query first to see if any posts have some comments with null gmt values, and some with initialized values. You’ll have to manually look through those to figure out correct comment order.