I tried Compiled Queries with a DbContext, with no success (it is not supported, and the workaround were not suitable for me too). Have you checed this link : http://blogs.msdn.com/b/efdesign/archive/2011/06/30/auto-compiled-linq-queries-entity-framework-june-2011-ctp.aspx ?
You can see this article : http://social.msdn.microsoft.com/Forums/en-US/0c07e1d6-7db6-4348-b106-e576d3153b70/ef-40-compiled-queries-performance?forum=adonetefx. I don't think using Compiled Queires make a big difference espacially with modern versions of EF (5 & 6).
On the first query, the connection is set up, and it can take some time.