What is the actual "spread speed" of water and lava in the context of a stone generator?

My observations are that it's somewhat random. I don't know why. I have a working piston-based generator that includes a simple edge-detection circuit so that the piston is only extended briefly – it doesn't get between the lava and water longer than is necessary to move the new block out of the way. I tuned the timing until it gave a consistent generation speed without extra piston-activations.

It ended up giving about 1 second between mining a block of cobblestone and the next one being pushed forward, which is a nice pace. As a side benefit, every time you hear the piston activate, the machine is generating a new block: there are no "empty" cycles or annoying extra piston noises.

Skip past the pictures for my conclusions about spread speed from the experience of building this machine.

This is the heart, an 8-tick clock:

Function: Generates an 8-tick cycle, 4-ticks on and 4-ticks off.

Layout: 3x2x1. The wire leaving the right of the image goes to the edge detector. This room is 5x4x2 and houses both the clock and the edge detector with some room to spare.

This is the edge-detection circuit, following this design on the Minecraft Wiki:

Function: This circuit takes the 8-tick clock as input and generates a 3-tick "on" output once per clock cycle, at the off-to-on edge. The 3-tick signal is from the difference between the two repeaters (4-1). I found that a shorter signal made the piston activate erratically, but you can tweak it independently of the clock (as long as it's shorter) to find the best pulse length. The Minecraft Wiki indicates that a regular piston should be fine with a 2-tick signal, and I don't remember why 3 ticks seemed like a good idea when I was building it. Recent updates to Minecraft may make a 2-tick pulse work just fine.

Layout: 3x2x2 plus 1 for input and 1 for output. The redstone wire leading out of frame to the left is from the clock and only one block long. The "on" pulse from this circuit leaves via the redstone torch that can be seen just poking out from behind the farthest dirt block. The wire leaving to the right (in front of the ladder) is connected to the piston.

This is the connection to the piston. Pretty simple:

Function: Powering the piston with the generated pulse.

Layout: This is the most flexible part of the layout. There's a 1-block up you can just see – this is the same 1-block up as visible to the right in the edge-detector image. The wire from the edge detector in my layout goes one block forward, up onto the next block for a total of a 2-block long wire, and powers the block beside the piston. This indirectly powers the piston and I did it that way just due to space constraints where I built. You can have a prettier layout easily.

For completeness, here's my lava and water sources:

Function: Violating conservation of mass.

Layout: The cobblestone at the bottom of the image is the same two blocks at the top of the previous image. The column of cobblestone between them going upward is the generated cobblestone output of the machine.

And the "user interface" of the machine:

Function: Harvesting tasty, tasty cobblestone.

Layout: You can see the "Incinerator" chute, which for reference is directly above my lava source block. The hatch in the back labeled "Cobblestone Generator Maintenance" is directly above the ladder in the other images. Behind the wall to the right is a hollow with some flowing water, so I can hold down the button while mining the top cobblestone block without breaking anything behind it. (The water brings blocks that have gone the "wrong" way back toward me. I find this setup preferable to using an obsidian backing because it doesn't degrade my picks, though it takes a bunch of extra behind-the-walls room.)

Note that the first time you break a block from the machine when it has a full complement of waiting cobblestone it will have anywhere from a 8-tick to 16-tick (about 1–2 seconds) delay in bringing up the next block, depending on where in the clock cycle you "woke it up".

From the experience of building this machine, I can't conclude definitively what the spread speed of lava and water is, but an 8-tick (~0.8 seconds) delay seems to be equal to or longer than the longest possible spread of two adjacent flow/source blocks – so it ensures that some cobblestone has been generated every cycle – without being unnecessarily slow.

From experience building simpler, no-piston generators (mostly for Skyblock maps), the spread does indeed seem to have a random component, as you've observed. Sometimes the water flows first, sometimes the lava. Despite this, the random component never seems to make it longer than 8 ticks after an in-the-way block is removed.