One difference between RSA and ElGamal is that ElGamal isn't necessarily deterministic (while RSA is).
What makes it non-deterministic? Is this advantageous to security? How else does this property affect ElGamal encryption or the ElGamal signature scheme?
In this context, "nondeterministic" means that the algorithm to generate the ciphertext (or the signature) takes a random value as one of its inputs, and it can generate many possible ciphertexts (or signatures) based on the random value. ElGamal is nondetermanistic because the encryptor selects a random exponent as a part of encryption method.
For public key encryption, this randomization of the encrypted message is important. If the public key encryption algorithm was not nondetermistic (that is, the encrypted message depended only on the plaintext message and the public key), then someone with an encrypted message $M$ and the public key $PK$ and a candidate plaintext message $P$ could test if the decryption of $M$ was $P$ (simply by encrypting $P$ using the public key $PK$, and checking if the result was $M$).
Because of this, public key encryption is almost always nondetermanistic. Note that RSA is not an exception; while the core RSA algorithm is determanistic, actual RSA public key encryption also includes a padding method, and this padding method can (and generally does) include randomness.
For public key signatures, there is no corresponding requirement due to the primitive semantics that signatures be generated using some random input; however, some cryptography proof techniques do assume that the signature generation is also nondetermanistic. On the other hand, in the specific case of ElGamal signatures (DSA), it actually does require a random input, and it turns out that this input really does need to be random, and uniformly distributed.
