Hmmm... It does sound like your SharePoint solution is a bit slow on the first authentication, which could be due to a missing warm up. However, when this is for all users that is not possible.
It doesn't sound like an ADFS issue thou. Are you accessing your SharePoint through a Load balancer?