Как насчет этого:
var randomizer = new Random();
var results = from en in context.MyEntity
where en.type == myTypeVar
let rand = randomizer.Next()
orderby rand
select en;
Для этого можно использовать индексированные представления.
Читайте здесь для SQL 2005: http://msdn.microsoft.com/en-us/library/dd171921.aspx
Прочтите здесь для SQL 2008: http://msdn.microsoft.com/en-us/library/dd171921.aspx