I'm sure the correct answer to this depends on the type of pooled objects and the workload, so I'll detail my implementation a bit:
I have an ObjectPool used to pool long-running command-line processes. These processes communicate via stdin/stdout, and perform file/network operations. Many tasks complete much faster than others and may return processes to the pool quickly. All access to the pool must be thread-safe.
My question is, am I better off managing the pool with a LIFO/Stack, or a FIFO/ConcurrentLinkedQueue? My reasoning on both sides:
My first thought was: benchmark it! Both of your arguments seem reasonable. You should implement both strategies and do tests which of them results in the higher throughput.
The problem you describe in your question is similar to the process scheduling operating systems have to face. Hence, maybe it would be useful to make use of priorities. Use a PriorityQueue and assign different priorities to your tasks, which could change dynamically over time, for instance with Aging.
And last but not least, as was already pointed out in the comments you could try both ConcurrentLinkDeque and let some fetch the front objects and some the rear objects. Here, too, my advice is to try out and measure which balancing works best.