).
Afficher ta page normalement.
Faire une requête asynchrone pour l'éxécution du script long et pénible (j'espère que ton serveur n'a pas de timeout ?).
Démarer en parallèle des petites requêtes pour mettre à jour la page de manière progressive.
En gros côté serveur, tu génères une sorte de log des données (Je ne sais pas si on peut avec des sessions, mais ça serait le mieux) avec le gros script, et tu récupères ces données avec le script "léger" (et tu les formates, genre en JSON) qui est appelé régulièrement par javascript / XmlHttp.
Après, les modifications de la page sont à gérer par Javascript en fonction des infos reçues à chaque fois...