Paintbrush paints noisy strokes at low sizes

[Ofnuts]

• You are using a soft brush, did you try with Hardness 100?
  
• When you use the brush when zoomed, Gimp receives coordinates for the mouse that aren't exact pixel coordinates for the picture, so it has to interpolate. As far as I can tell, a small amount of stroke smoothing makes things look a lot better.