Hm, well right now the basic mechanic boils down to finding the first car with an open lane. To add challenge you either have to obscure the first car or add additional steps in-between. I think the first option is not much interesting so let's think about the second.
Typical parking games, add this difficulty by allowing cars to move 1 tile at a time, and you have to find the correct order of moves, sometimes doubling back to later move forward. But with your approach, the cars only go in a straight line if there is nothing in front.
One thing that comes to mind that could work within your ruleset are hidden tile turns. Imagine that each tile has a direction on top of it and it will force a car to turn. But you learn where those are only after some of the cars move, so the rules on that board change a bit as the game progresses and you have to adapt.
Other, simpler way, would be to more artificially add some blockers, change cars' directions etc., implementing a change that requires you to reconsider and find the solution again.
Another way would be to lessen the amounts of cars but introduce 'game changing elements' like ramps, turns - things that will modify how the cars will go. This will cause the player to have to think more thoroughly about each move, because it is harder to imagine a complex set of actions than just going in a straight line.
On top of that, you can add a new type of element every 10 or so levels and later on make combinations of them for more variety. In this approach I imagine the player feels like they could move more than one car each turn on first glance, but upon further thought they realize that some moves will lead to accidents, so in the end they find the right solution.
I imagine features like a moving explosive, which moves on every car triggered, so players have to plan out the movements with future explosive placement in mind.
I think this last way is the most viable and simplest to add. But the levels would probably require more designing but that is the fun of creation :) enjoy!
@edit
Also, you could lower the amount of levels until you reach the larger sizes of the board. I played through 30 levels and lost interest. If a larger size appeared at level 20, I think the game would keep my attention a little bit longer. 500 levels is a lot, this game doesn't really need that many for the amount of thought it requires :p