Actually, after a few minutes pondering, I'd like to attempt an answer myself, based on symmetry.
The Lagrangian cannot depend on individual velocity components (but it can depend on the overall magnitude of the velocity) because of rotational symmetry - with no external forces acting on the particle, how could the direction of it's velocity have any impact on the physics of the situation?
As for the positional coordinates, I presume these can't affect the Lagrangian because of translational symmetry. (Again, with no external forces acting on the particle, the location has no bearing on its energy, which after all is what the Lagrangian describes)
Have I got the right idea here, or am I making false assumptions?