UDF And Query Plan Caching
It's unlikely it's related to the query plans.  I've only every seen very complicated queries take more than 1 second for the plan to get created, much less 4 seconds as your describe.

It sounds like it's page caching - basically SQL Server keeps recently used data in memory.  The first run with each set of parameters you are paying the (normally expensive) cost of physical disk access.

Subsequent executions can access the data pages which are already stored in memory without waiting for the disk subsystem.