Well, problem somewhat solved. I went through and carefully optimized the structure of the Xcart database. Tough to do and still ensure that nothing is broken. Then I commented out the $category_condition statement and put the old 3.5.7 one in its place. Not as thorough, but at least our site is loading in a reasonable time now.
This is what I used, if anyone is wondering.
Code:
$category_condition = " AND $sql_tbl[products].categoryid=$sql_tbl[categories].categoryid";