Firebase actualmente no garantiza un tiempo de entrega aproximado para las push, eso depende, de la conexion del dispositivo al que le llega, de la conexion y la arquitectura de los servidores para manejar esos datos a cada usuario (a algunos les puede llegar mas rapido que a otros).
Hay muchas preguntas de este tipo en el sitio de SO en ingles y algunos issues abiertos en github
https://github.com/firebase/quickstart-android/issues/83
Muchas veces tiene que ver tambien con la prioridad de como se esten enviando esos mensajes, en la documentacion oficial encontramos lo siguiente
Configuración de la prioridad de un mensaje En Android, hay dos
opciones para asignar una prioridad de entrega a los mensajes
descendentes: prioridad normal y alta. La entrega de los mensajes con
prioridad normal o alta funciona de la siguiente manera:
Prioridad normal. Esta es la prioridad predeterminada para los
mensajes de datos. Los mensajes con prioridad normal se entregan de
inmediato cuando la app está en primer plano. Cuando el dispositivo
está en Descanso o la app está en App Standby, se puede retrasar la
entrega para ahorrar batería. Para los mensajes menos urgentes, como
las notificaciones de correos electrónicos nuevos, la sincronización
de IU o la sincronización de datos de app en segundo plano, selecciona
la prioridad de entrega normal.
Cuando recibas un mensaje de prioridad normal en Android que solicite
una sincronización de datos en segundo plano para tu app, debes
programar un trabajo FJD o un JobIntentService para gestionarlo cuando
la red se encuentre disponible.
Prioridad alta. FCM intenta entregar los mensajes de alta prioridad de
inmediato, lo que permite que el servicio de FCM active un dispositivo
inactivo cuando es necesario y ejecute un procesamiento limitado
(incluido el acceso de red altamente limitado). En general, los
mensajes con prioridad alta generan la interacción de los usuarios con
la app. Si FCM detecta un patrón en el que no lo hacen, puede reducir
la prioridad de los mensajes.
Como una pequeña porción de la población móvil de Android se encuentra
en redes de alta latencia, evita abrir una conexión a tus servidores
antes de mostrar una notificación. La devolución de llamadas al
servidor antes del final del tiempo de procesamiento permitido puede
ser algo arriesgado para los usuarios en redes de alta latencia. En
lugar de eso, incluye el contenido de la notificación en el mensaje de
FCM y muéstralo de inmediato. Si necesitas sincronizar contenido
adicional de la aplicación en Android, puedes programar un trabajo FJD
o un JobIntentService para gestionarlo en segundo plano.
Puedes referirte a esta documentacion para leer y entender mas como funciona
https://firebase.google.com/docs/cloud-messaging/concept-options#configuracin-de-la-prioridad-de-un-mensaje
Pero para cerrar, es muy improvable saber con exactitud cuando le va a llegar un mensaje a un determinado usuario, imaginate enviar 500.000 notificaciones y que tengan que llevar todas en 5 o menos segundos, eso va a depender en muchisimos factores como te comentaba arriba, el tiempo que tarda el mensaje en llegar a cada telefono puede diferir.