I'll bet it's not so much the distance, but the number of data points (i.e., bends in the road and specific turn instructions).

That makes sense. The more data there is because of the road itself (turn, exits), points of interest or other factors, the more data there will be to download.

In that case I'm particulary unlucky, because Belgium's road network is one of the most dense in the world.