I poked around in the source code and looked at the nagios main loop. Half of nagios is essentially an event scheduler: perform task X, then put it back in the run queue to run in Y seconds. We have around 3200 tasks, most scheduled on 5 minute intervals, but some run every minute and some run every hour and some run somewhere in between.
To do this, nagios keeps a singly-linked list of all tasks and, when inserting an task, walks the list until it finds the right place. D'oh.
(I have to actually profile before I consider this the main cpu-hogging part of nagios, but it doesn't give me hope for the quality of the rest of the system.)