Given that the printer is connected to the Linux machine, when you print from a Linux login you are using the CUPS printer software. That is probably loaded when you boot the system. There is a CUPS daemon. Most start up configurations will load that by default.
When you print from the XP box you are interacting with Samba, as you already know. It is possible that the Samba software does not load its own printer module when Samba starts. Therefore it is possible that it has to load its printer module when you print from XP. That could account for the delay.
Try this. Print two or three different documents from the XP machine at the same time. If you only have the delay for the first document then my theory may be correct. If you have a long delay for each document then my theory is probably wrong.
Another possible consideration is the amount of memory that the Linux machine has free. If it has to swap processes in order to load the document then that will delay the print spooler. However, this would probably affect local print jobs as well as network print jobs.