Finally a decent brush!
I've finally discovered how to do a decent brush in Krita. Turns out that the most time-intensive bit was the redrawing of the picture. This happened a lot in the in-betweening code, that painted a line between the previous and the current mouse position if Krita couldn't keep up with the mouse.
So, now I update only once per mouse-move event, and all is pretty:
It's not as good as the Gimp's brush, and circles tend to come out a bit angular, but I am pretty chuffed with this result anyway.