manera eficiente de implementar la paginación

Tratando de darte una breve respuesta a tu duda, si ejecutas el skip(n).take(m) métodos en linq (con SQL 2005/2008 como servidor de base de datos) su consulta utilizará Select ROW_NUMBER() Over ... declaración, con es de alguna manera paginación directa en el motor SQL.

Poniéndote un ejemplo, tengo una tabla db llamada mtcity y escribí la siguiente consulta (funciona también con linq a 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.
}

La 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 es un acceso a datos en ventana (muy bueno, por cierto, porque devolverá datos desde el principio y accederá a la tabla siempre que se cumplan las condiciones). Esto será muy similar 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

Con la excepción de que esta segunda consulta se ejecutará más rápido que el resultado de linq porque utilizará exclusivamente el índice para crear la ventana de acceso a datos; esto significa que, si necesita algún filtrado, el filtrado debe estar (o debe estar) en la lista de entidades (donde se crea la fila) y también se deben crear algunos índices para mantener el buen rendimiento.

Ahora, ¿qué es mejor?

Si tiene un flujo de trabajo bastante sólido en su lógica, será complicado implementar la forma SQL adecuada. En ese caso, LINQ será la solución.

Si puede bajar esa parte de la lógica directamente a SQL (en un procedimiento almacenado), será aún mejor porque puede implementar la segunda consulta que le mostré (usando índices) y permitir que SQL genere y almacene el Plan de Ejecución del consulta (mejorando el rendimiento).