Most of these sizes can't plausibly be completely searched, but these are the best positions I could find so far, using my pessimal program and trying alot of possible goal positions. Those puzzles are marked with a ? in the chart. I've also included a lot of puzzles that I haven't proved to be optimal - a lot of them probably aren't. For the biggest of these, it took some hundreds of hours on my machine to check all possibilities.

The goal position with the largest possible distance, plus a start position at that distance, is the longest puzzle of that size.

For each goal, run an optimized version of the pessimal program to find out how many moves away a start position can be. For a given size, loop through every possible placement of goals. I only considered grids with no internal walls, because allowing internal walls would vastly increase the search space, and I haven't found a way to efficiently deal with that yet. I've used a variant of my pessimal program to determine the longest possible Sokoban puzzle, in move count, that fits in a rectangular grid of a particular size. Note that I have a few puzzles on Sokoban Online that aren't in here, because they use that site's Modern elements like colored blocks and ice. As of 4 they include 22 handmade puzzles already published on Sokoban Online, 56 rectangular puzzles as seen below, 31 puzzles found with the pessimal program, 17 handmade puzzle variants or ideas that weren't my best, 32 puzzles made with YASGen, for a total of 159. Here is a collection of all the different puzzles I have made. Let's call it the 'pessimal program' - pessimal means worst possible, as in furthest from the goal. It will search the entire graph of possible positions, if enough memory is available, and print the positions it finds at the edge of its universe as well as how many moves it takes to get there. My contribution to the computer side of things is a program that finds the longest puzzles with a given goal position or a given start position. I use JSoko and Sokoban YASC and play on Sokoban Online. There are some very powerful puzzle solvers and solution optimizers out there, as well as a program called YASGen that uses a genetic algorithm to generate difficult puzzles. Solving and designing puzzles by hand is a lot of fun, and with computers, there is an added level of depth. Sokoban is an interesting and deep puzzle that I've been interested in for a couple of years.

Online sokoban solver