You are right, it seems it has to do with application pool recycling.
Recycling the pool will clear all caches and will cause new JIT compilation for all newly requested assemblies. A lot of things are happening when the application or certain parts of the application are called for the fist time in the application’s lifetime. For example, when the admin part is opened for the first time, some data providers such as Versioning and Workflow are loaded and cached. If you are using only the public part, these providers will never be loaded. Proper configuration of the pool is extremely important for the performance. For example, you may configure it so the worker process is recycled based on memory usage instead of time.
Of course, there are some optimizations that we can make to speed up the first calls but they will always be slower.