I'm quite surprised that the "holy grail of paging" doesn't mention the (granted a bit less popular) "seek method" as described here:
Take the following example:
SELECT TOP 10 first_name, last_name, score
WHERE (score < @previousScore)
OR (score = @previousScore AND player_id < @previousPlayerId)
ORDER BY score DESC, player_id DESC
The @previousScore and @previousPlayerId values are the respective values of the last record from the previous page. This allows you to fetch the "next" page. If the ORDER BY direction is ASC, simply use > instead.
With the above method, you cannot immediately jump to page 4 without having first fetched the previous 40 records. But often, you do not want to jump that far anyway. Instead, you get a much faster query that might be able to fetch data in constant time, depending on your indexing. Plus, your pages remain "stable", no matter if the underlying data changes (e.g. on page 1, while you're on page 4).
This is the best way to implement paging when lazy loading more data in web applications, for instance.