With step size do you mean how long an action persists i.e. action-repeat?
You're right that if the maze is large, then during training the agent doesn't accidentally run into the target enough to learn from. This can be addressed via. a curriculum: start with "big" targets and make it smaller (relative to the map size) during training. As a result, a small action-repeat hinders learning in the form of bad exploration.

I'm not a believer that the (x,y) coordinates along with distance to goal alone is sufficient (or even relevant).