Many years ago I investigated [1] the problem of Rush Hour with minimal size cars. I called it Unit Rush Hour, as the cars are just 1x1, but restricted to either horizontal or vertical movement. Interestingly, the puzzles can also be viewed as a kind of maze with restricted movement. My web page has the hardest 4x4 and 5x5 instances in playable form.
I found the hardest 6x6 puzzle to require a whopping 732 steps [2].
[1] http://tromp.github.io/orimaze.html
[2] http://tromp.github.io/rh.ps