I've seen this kind of behavior. i may guess that you configure the kernel with PREEMPT, assuming it will solve the problem for you.

I'll split the problem into two:
1. program loading stage is finished (+ reschedule)
2. thread execution time (delay)

when executing a new application it's involved with plenty of kernel activity such as fetching the application from storage, loader relocation,allocating and remapping pages, resolving dynamic linking etc..., all the activity occurs under the hood of the kernel, suspending most of the kernel activities, due to many spin locks on the way. that delays other kernel threads as well, and even workqueues.

trying to bypass the symptom  - re-running the exact external application ,  should not be involved with a second delay, as it was cached. so may be running the external application in advance may be good enough for you.

what you actually need is a better kernel preemption such as  using Ingo Molnar 's  PREEMPT_RT patch. (it may reduce performance a little).

the second part is that the scheduler delays the thread execution as it think other kernel's entities has a higher priority such as softirqs, workqueue, etc...

the PREEMPT_RT may solve this problem as well as it bring a better priority control, with the addition of priority inheritance.