В EF първата заявка се изпълнява, тя трябва да бъде компилирана, въпреки че програмата вече е изпълнена.
Предлагам да прочетете това http://www.codeproject.com/Articles/38174/How-to-improve-your-LINQ-query-performance-by-X и това https://msdn .microsoft.com/en-us/library/vstudio/bb896297%28v=vs.100%29.aspx и опитайте отново, за да видите дали това помага.
Успех!