Update on this: apparently the slow queries were not caused by the template but by the WordPress related posts feature it was using. Thanks for Themex (who created the Midway template) for spotting the issue.
I deactivated it and now the site seems fine (fingers crossed).