CSS não carrega na primeira visita

Olá pessoal, tudo bem?

Estou com uma dúvida um pouco chata.

Tenho um menu todo ele feito em ul - li e CSS que estranhamente não está carregando na primeira visita que se faz no site, mas na segunda ele carrega normalmente.

Aleguei aqui com o pessoal que era cache, mas eles entraram em navegadores que nunca tinham entrado no site, e ocorreu o mesmo problema.

Alguém já passou por isso?

O que pode ser e como resolver.

Abraços.