The wikipedia-Link to Klotski states that the minimum number of moves is 81. This page claims that there is a rush-hour-configuration which needs at least 93 moves to solve it.

However I can't say which of these solutions is easier to find ;-)