> - Allow filtering, sorting, and pagination: yes, good luck coming up with the right query structure and sticking to it.

I believe that treating RESTful APIs as a smart data storage that can do advanced querying is a mistake, or rather REST is not the proper solution for this use case, and you did well to move on from it. Personally I've never failed to use REST successfully as long as I was willing to do proper caching, sorting and filtering in the API consumer. REST is plenty if you need presenting collections of things with key-set pagination and proper caching headers.

In the days of HTTP2+, it's easy to fire 100 concurrent requests to a key-set RESTFUL API and load all the data that you could ever need. :)