Cracking lowest plaintext bit in Padding oracle attack with PKCS#5
Why do all the implementations of this attack assume that the first success from Oracle means we got a 0x01 in the last byte from the oracle? Is it because the probability of getting a 0x02 in the last byte and the penultimate byte while only varying the last byte is lower?


Largely, yes.  Remember, our general assumption is that an attacker is happy with an attack that only works most of the time.  In this case, assuming that the attacker has no initial information about the plaintext block under attack, then a random C1 that causes us to have valid padding would correspond to an 01 padding byte with probability circa $1 - 1/255$ of the time.

In addition, if you find a C1 that might reveal the last byte, and might have a longer padding pattern, there's a very easy test; try C1 with the penultimate byte modified; the resulting decryption will still have valid padding if it had an 01 padding byte, and have invalid padding if it was anything else; hence it would be easy to catch.