One way in which many old-skool games solved (or hid) this problem was to animate the sprite.
That is, if your sprite was going to move less than one pixel per frame (or, especially, if the pixels/frame ratio was going to be something odd like 2 pixels in 3 frames), you could hide the jerkiness by making an n frame animation loop that, over those n frames, ended up moving the sprite by some k < n pixels.
The point is that, as long as the sprite always moves in some way on each frame, there's never going to be any single frame where the whole sprite would suddenly "jerk" forward.
I couldn't find an actual sprite from an old video game to illustrate this (although I think e.g. some of the digging animations from Lemmings were like that), but it turns out that the "glider" pattern from Conway's Game of Life makes a very nice illustration:
Animation by Kieff / Wikimedia Commons, used under the CC-By-SA 3.0 license.
Here, the little blocks of black pixels crawling crawling down and right are the gliders. If you look carefully, you'll notice that they take four animation frames to crawl one pixel diagonally, but since they move in some way on each of those frames, the movement doesn't look that jerky (well, at least not any more jerky than anything looks at that frame rate, anyway).