How do RSA and ElGamal key sizes compare? I have a rather silly question regarding the comparison of RSA with ElGamal over integers. If you want to compare their performance in the same level of security, does the modulus of both of them need to be the same size, or does RSA have to be double the size of ElGamal?
RSA and ElGammal are about equally secure at the same modulus size (assuming, of course, intelligent parameter selection in both cases).

For RSA (assuming you use good padding), the best known-attack is to factor the modulus with NFS.

For ElGammal (assuming you use a subgroup with a large enough prime factor), the best known-attack is to compute the discrete log of the public key with NFS.

Now, the version of NFS to compute discrete logs is somewhat more complicated than if it were used to factor; however I don't believe that extra complication adds a significant time to the time taken.