I am assuming none of these padding algorithms are "the best"... But what are the advantages and disadvantages of using them? PKCS7 is certainly the most commonly used one, but I am interested in seeing what the others offer.
ANSI x.923 padding and the padding used within PKCS#7 are functionally equivalent. The last byte of the padding stream is the length of the padding stream. The difference is the value of the other bytes, which are all 0x00 in ANSI, and all the identical to the last byte in PKCS#7.
f4 93 d6.00 00 00 00 00 00 00 00 00 00 00 00 0d ANSI X.923 f4 93 d6.0d 0d 0d 0d 0d 0d 0d 0d 0d 0d 0d 0d 0d RSA PKCS#7
Neither has a large advantage over the other, except that a zero padded message can be "fixed" to ANSI padding by simply changing the last byte in many cases.
I do not believe that either one requires official verification of the padding bytes preceding the last byte to verify that they are correct per the standard, meaning the same algorithm can decode either scheme by simply looking at the last byte. The same algorithm will also decode ISO 10126 padding.
If used in an unauthenticated scheme, the bytes should be checked for correctness, since some attacker advantage could be achieved through their manipulation. Verification is done with bitwise OR against those bytes, which then must either equal 0x00 for ANSI or the length byte for PKCS#7 padding.
Both only support up to 255 bytes of padding.
PKCS is by RSA for RSA products and algorithms, and ANSI is a generic common standard by committee with the goal of interoperability.
ISO/IEC 7816-4 is a different story. It is more flexible and can technically support an unlimited length of padding bytes, however removal of the padding can be more computationally intensive. ISO/IEC 7816-4 padding places a single 0x80 byte after the message, then pads the rest with 0x00.
The padding scheme is also known as bit padding, as it simply places a single 1 bit after the plaintext, followed by 0 valued bits up to the block size; it therefore works for bit oriented protocols as well.
f4 93 d6.80 00 00 00 00 00 00 00 00 00 00 00 00 ISO/IEC 7816-4
By specification you must start at the end and work backwards, checking every byte until you hit 0x80. If you hit something other than 0x80 or 0x00 the message is assumed to be incorrectly decoded. With a small block size this is quite fast.
ISO/IEC 7816 contain the ISO/IEC standards for electronic ID cards like smart cards. Systems that use the standard have mandatory padding for encrypted data.
I have also seen what I called "rainbow" padding, which looked to be a hybrid of ANSI and PKCS7. The last byte was the amount of padding bytes, and the preceding bytes were that value decrementing until the message boundary:
f4 93 d6.01 02 03 04 05 06 07 08 09 0a 0b 0c 0d ???
I have never seen it described by a specific name, but it may be removable by an ANSI/PKCS remover if the remover only takes the last byte into account.
As you mentioned, none of these padding schemes are perfect. Only IEC 7816 can support block sizes of 256-bits and larger, and ANSI and PKCS7 can be unpadded by a common algorithm.