Entity Framework Skip/Take is very slow when number to skip is big

You are right on that, Skip().Take() approach is slow on SQL server. When I noticed that I used another approach and it worked good. Instead of using Linq Skip().Take() - which writes the code you showed - , I explicitly write the SQL as:

select top NTake ... from ... order by ... where orderedByValue > lastRetrievedValue 

this one works fast (considering I have index on the ordered by column(s)).

I think OFFSET .. FETCH is very useful when browsing the first pages from your large data (which is happening very often in most applications) and have a performance drawback when querying high order pages from large data.

Check this article for more details regarding performance and alternatives to OFFSET .. FETCH.

Try to apply as many filters to your data before applying paging, so that paging is run against a smaller data volume. It is hard to imagine that the user wants no navigate through 1M rows.

Navigating though a million records in a database will always be slow in comparison to other ways, the database has to "skip" a million records, it does this by creating the result in memory and then discarding the first million rows.

Have you thought about a non-sql alternative (solr, lucene, etc), at least to get the ids of your rows first and then using a where id in () query?

Alternatively you could have a Search table (cooked up table) of your main table with only the bare minimum data and the Ids, so you can skip over that and get the ids and query the big table with those.