Well, other than that, I really can't think of why the gallery as a whole might be slow. It can't be pin-pointed to one particular feature of the gallery since the gallery is slow on every page (and most pages don't have the random image stuff, etc).
<opinion>I don't think it's a problem with the gallery. My site doesn't get quite as many hits, but it still gets a decent chunk of traffic, and I have had no problems. If you think about it, the script is just PHP and MySQL, which runs very fast. I just dunno, but I don't think it's the script.</opinon>