The delay on first execution is unlikely to be the execution plan. Far more likely to be loading the data into cache. Plans just don't usually take that much time to generate.
You can test it out, on a dev server, using DropCleanBuffers or FreeProcCache to do one of the two, then see where the slow down is actually coming from.
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability