Vou lhe dar um palpite aqui:Cache de banco de dados.
Na primeira vez que você executa a página, a consulta não é armazenada em cache no banco de dados, portanto, leva mais tempo, expirando o limite de tempo do PHP.
Nas outras vezes, a consulta é muito mais rápida.
Você pode dividir a consulta, como mencionou, ou tentar aumentar o limite de tempo no script:
set_time_limit(0); //No time limit
set_time_limit(60); //60 seconds
Para ter certeza, você pode usar este para limpar o cache do banco de dados e usá-lo sempre assim você sempre executará a página no cache limpo.
