Initial page loads (MySQL?) are painfully slow...

I'm using my site for a Gallery2 installation right now, and it works well for the most part. However, on an initial page load/connect, there's a delay of at least 8-10 seconds before the page actually starts loading. I'm reasonably sure this is because of the MySQL database connect. When I reload within a minute or two of loading another page, the speed is much better, maybe 2-4 seconds. However, if I try to go back even a few minutes later, it takes a longer time to load again.

If this isn't the MySQL connection, then what could it be? And if it is - how would I go about fixing or working around it? I want to experiment with persistent connections, but that would require dropping out of PHP-CGI mode, which unfortunately disables the exec() command, which I really need for Gallery. I don't suppose there's any way to install my own non-CGI PHP so that I could use both exec() and persistent connections..?

In any case, it seems that there shouldn't be a 10 second delay before my site loads when someone first visits it. Any suggestions are much appreciated.

My Expression Engine site and I wait with bated breath for the answer to this question. In the meantime, we feel your pain.

I thought I'd give this a little bump here...everything is back to normal after this week's power outage, but unfortunately that "normal" still seems to mean slow MySQL servers...