maneira eficiente de implementar paginação

Tentando dar uma breve resposta à sua dúvida, se você executar o skip(n).take(m) métodos no linq (com SQL 2005 / 2008 como servidor de banco de dados) sua consulta estará usando o Select ROW_NUMBER() Over ... instrução, com é de alguma forma a paginação direta no mecanismo SQL.

Dando um exemplo, eu tenho uma tabela db chamada mtcity e escrevi a seguinte consulta (funciona também com linq para entidades):

using (DataClasses1DataContext c = new DataClasses1DataContext())
{
    var query = (from MtCity2 c1 in c.MtCity2s
                select c1).Skip(3).Take(3);
    //Doing something with the query.
}

A consulta resultante será:

SELECT [t1].[CodCity], 
    [t1].[CodCountry], 
    [t1].[CodRegion], 
    [t1].[Name],  
    [t1].[Code]
FROM (
    SELECT ROW_NUMBER() OVER (
        ORDER BY [t0].[CodCity], 
        [t0].[CodCountry], 
        [t0].[CodRegion], 
        [t0].[Name],
        [t0].[Code]) AS [ROW_NUMBER], 
        [t0].[CodCity], 
        [t0].[CodCountry], 
        [t0].[CodRegion], 
        [t0].[Name],
        [t0].[Code]
    FROM [dbo].[MtCity] AS [t0]
    ) AS [t1]
WHERE [t1].[ROW_NUMBER] BETWEEN @p0 + 1 AND @p0 + @p1
ORDER BY [t1].[ROW_NUMBER]

Que é um acesso a dados em janela (muito legal, aliás, porque estará retornando dados desde o início e acessará a tabela desde que as condições sejam atendidas). Isso será muito semelhante a:

With CityEntities As 
(
    Select ROW_NUMBER() Over (Order By CodCity) As Row,
        CodCity //here is only accessed by the Index as CodCity is the primary
    From dbo.mtcity
)
Select [t0].[CodCity], 
        [t0].[CodCountry], 
        [t0].[CodRegion], 
        [t0].[Name],
        [t0].[Code]
From CityEntities c
Inner Join dbo.MtCity t0 on c.CodCity = t0.CodCity
Where c.Row Between @p0 + 1 AND @p0 + @p1
Order By c.Row Asc

Com exceção de que, esta segunda consulta será executada mais rapidamente que o resultado do linq, pois estará utilizando exclusivamente o índice para criar a janela de acesso aos dados; isso significa que, se você precisar de alguma filtragem, a filtragem deve estar (ou deve estar) na listagem de Entidades (onde a linha é criada) e alguns índices devem ser criados também para manter o bom desempenho.

Agora, o que é melhor?

Se você tiver um fluxo de trabalho bastante sólido em sua lógica, a implementação da maneira SQL adequada será complicada. Nesse caso, o LINQ será a solução.

Se você puder baixar essa parte da lógica diretamente para o SQL (em um procedimento armazenado), será ainda melhor porque você pode implementar a segunda consulta que mostrei (usando índices) e permitir que o SQL gere e armazene o Plano de Execução do consulta (melhorando o desempenho).