No EF, a primeira vez que uma consulta é executada, ela deve ser compilada, mesmo que o programa já esteja concluído.

Eu sugiro a leitura deste http://www.codeproject.com/Articles/38174/How-to-improve-your-LINQ-query-performance-by-X e este https://msdn .microsoft.com/en-us/library/vstudio/bb896297%28v=vs.100%29.aspx e tentar novamente para ver se isso ajuda.

Boa sorte!