Typically Entity Framework (EF) itself takes the major portion of the start-up time on the first start when EF builds model and EQL views, all other queries run very fast. It is a known EF behavior (see http://blogs.msdn.com/b/adonet/archive/2008/06/20/how-to-use-a-t4-template-for-view-generation.aspx).
Also connection open takes additional time on the first execution, as it is a usual situation with database connections.

So a solution is not to destroy your AppDomain after the first query. It is not an ideal solution yet, but it works well for Web applications and Windows services, or for someone who can use idle time to warm up a Windows desktop application also.

There is a room to improve start-up time within SSAS Entity Framework Provider itself too, so its next versions can have some improvement.