Huge delay on first request due to many slow SQL queries
So this is how I fixed the problem. It is not a real solution as I could not nail the exact source of the problem (if there is one).

1) Aggregate CSS (cache settings). This reduced the latency by half
2) Set cron to never (and run it externally)
3) Set up a cron job that calls the home page with Lynx every 30 minutes