So just an update on this.
We still have one remaining lag issue. I know where exactly in the code that the SQL query-o-doom is that is causing it but the query itself cannot be fixed. I've tried experimentally rewriting it several different ways without success. The only way to fix it is to break it into two queries and write a lot of additional php code to do the additional processing.
The problem is caused when some users click the "Unviewed" button in the gallery. For some users, the subsequent query takes 4 to 5 seconds to run. Users who have been looking at almost every pic in the gallery since the new gallery opened are incurring this delay. So for those using this option, if every time you click it you see this delay, then your user account is one of the ones incurring the lag. While that query runs, everything else has to queue up behind it.
This is not the fault of the users utilizing that function, it's just revealing a poor software design decision by the SMF gallery developers. I hope to have a chance to see if I can fix the code, but if I can't and the lag get's worse, I may have to take that feature away.