On NAND or NOR flash, is program time completely independent of byte values?
Short answer:

There might be a data-dependent duration, especially on devices already programmed and erased many times.

Not so short answer:

Normally, programming does not involve a single pulse1. The number of pulses depends on "how fast" the correct data is achieved.

In fact, the Flash chip has its internal state machine that checks if the cells where programmed at the correct values. If there is a bit, which has not been programmed at 0, then a new pulse is generated. This is repeated "some" times.

This is required because, beside cell-to-cell dispersion, with many program-erase cycles, a small amount of charge gets trapped, especially in the silicon nitride layer, that forms the ONO (Oxide-Nitride-Oxide) stack of the interpoly dielectric, sandwitched between the floating gate and the control gate. Also, defects can be generated in the dielectris, reducing the retention time. Bad blocks must be also identified in NAND Flash, to allow the device to be still used, without compromising the chip functionality. 



Therefore, if you start with a byte at 0b1111111 (erased) and you want to program a 0b00001111, then the chip needs to check that all the 4 programmed (cleared) bits are in the correct range. This is done in parallel, but additional pulses might be given to those bits, which are not identified as "0". Of course there will be a maximum number of pulse, and if the bits are still not at the correct value, an error is typically signalled. 

The worst case, in terms of time, is when you program a 0b00000000, as the probability that a bit is not at "0" after the first pulse il larger.

If you program a 0b11111111, there won't be any pulse at all2, as the bits are already supposed to be at that value, after erase.

Finally, erase is done on per block-basis, but the smart algorithm ensures that all the cells have all the same "1" value.  This is not trivial, as over-erase in NOR flash is deleterious: if the threshold voltage of one cell gets too low, you get with a stuck at 1 bitline.



NOTES:

1The programming methods could be Fowler-Nordheim tunneling, in NAND Flash, or channel hot carrier injection, in NOR Flash. Therefore, the pulse might be at the gate or both at gate and drain. Still, even on CHC, this is considered a single programming pulse (it happens "almost concurrently").

2 Actually, the state machine might generate the first pulse, but it is gated with the ~0b11111111 mask, so the cells do not receive the pulse. The state machine will then identify that all the bits have already the correct value (they were erased, and they stay erased) so no further pulses will be generated.