Hay soluciones con javascript solamente. La página carga en el fondo mientras se muestra el mensaje de "cargando...".
Al usar las funciones de salida de PHP lo que haces es "guardar" los datos que vayan saliendo al navegador hasta que haciendo el flush del buffer los envias ya procesados. Pero si la página HTML que generas y que tienes que enviar es muy larga, entonces igual el usuario irá recibiendo en su navegador el código HTML progresivamente, y dependiendo de éste, lo irá mostrando poco a poco.
Con javascript, que creo es lo que necesitas, puedes mostrar desde el comienzo un aviso (Cosa que no puedes hacer con php) (mejor dicho, si puedes, pero te genera HTML inválido, es incorrecto, etc. etc.) que desaparezca al finalizar la carga.
