You can arrange for indexes on the most commonly used columns, so that e.g. initial default page load is fast, while leaving the user hanging for up to a second or two on the more unusual queries.
It turns out that when people have better filtering and sorting tools, they spent a lot less time digging for page 10,001.
Even experts fall into this trap, actually:
https://sqlperformance.com/2015/01/t-sql-queries/pagination-...
I've invested several months of my life optimizing arbitrary sort and filter for MySQL results over tables varying from 100k rows to 100M (using time windows to scope things). As long as you can efficiently cut down the underlying data set into the region of 100k using some kind of window - usually recency based - and convince MySQL to filter by this before it sorts or does any other kind of filter - then limit / offset pagination doesn't hurt.
You can then use higher-level pagination on the recency window if it becomes necessary.
Who else is to blame? Should every vendor turn the documentation into a textbook on relational databases and their intrinsic properties?
One can only hope.