It's also a shame that this paper in turn doesn't cite "Testing Heuristics: We Have It All Wrong" (J. N. Hooker, 1995) (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71....), which discusses these issues in much the same way. It's good to see in "The Benchmark Lottery", however, that they look more into specific tasks and their algorithmic rankings and provide some sound recommendations.

One thing that I'd add (somewhat selfishly as it relates to my PhD work), is the idea of generating datasets that are deliberately challenging for different algorithms. Scale this across a test suite of algorithms, and their relative strengths and weaknesses become clearer. The caveat here is that it requires having a set of measures that quantify different types of problem difficulty, which depending on the task/domain can range from well-defined to near-impossible.