If you want to sort by any column and paginate on any column (so you can have your cursor), a BTREE (MySQL index) is sort of the wrong structure in the first place. You probably want a document store for something like this. Scylla!

More pragmatically, just force bookmarked scans - limit the columns that can be sorted by - use a replica with indexes that the writer doesn’t have - pay for fast disks - use one of the new parallel query engines like Aurora or Vitess - just tell the business people to wait a dang minute, computer is thinking!