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.
As mentioned by @zzzzBov, what you are looking for is called falling edge detector. The wiki has a section on these, with multiple options to choose from, like these two:
On the left, the sticky piston retracts the diamond block, allowing a signal to go through before the repeater turns off. When the power is turned on, the diamond block cuts off the signal before the repeater turns on.
The design to the right works using locked repeaters. When you unpower the input, the repeater on the right is unlocked just briefly enough to allow a signal through. On powering the input, the repeater is locked before it can change state.
Another option you have is to use a rising edge detector, also known as a monostable circuit, and invert the input using a redstone torch. There's plenty of designs available online.
Best Answer
The observer ceases 'observing' for the duration of emitting its own redstone pulse - only changes occurring after it are noticed. The first pulse ends before the piston starts extending. Then the piston extends, the observer notices it, but the piston starts retracting immediately. The observer would emit the signal while it's in transition upwards, except blocks in motion don't emit redstone signal, so it's suppressed. Still, the 'cooldown' is initiated and the changes occurring during the motion - ignored. It arrives at the 'rest' position right as its redstone signal ends, and only then starts observing anew.