I can think of two possible reasons:
(1) Most likely: After the first run , the data pages that the query needs to read are already cached in memory, so that in subsequent runs it can read the data directly from memory without going back to the disk. (On a busy server with not enough memory, during the day those data pages might get flushed from cache, but i guess that's not happening on your system.)
(2) Less important: After the first run, the execution plan for the SP is already in memory, and SQL doesn't have to re-develop the plan for subsequent runs (i.e. it will already know how to carry out the query). But normally, query plans don't take so long to prepare that it would account for the difference you are seeing.
So, there's probably not much to do re: speeding up the first run. If it makes sense, you could perhaps have the SP automatically run when the system starts, or maybe have a scheduled job run the jos early before the users get at it. But often that's not really practical: it is very situation-specific.
If anyone else can shed more light on this, they'll probably post their comments here.
bperry