Encrypting a message for multiple recipients

This problem is often called broadcast encryption: how can you set up a system that will enable transmission of an encrypted message to an arbitrarily chosen subset of the people involved? There's a trade-off between two difficulties. If you just give each user an individual key in a generic public key cryptosystem, without setting up some sort of special system, then there's nothing you can do except to append all the encryptions, which is a problem if the number of users is huge. (Imagine broadcasting an event to a billion subscribers. Adrien's observation is an important point, but it doesn't change the scaling.) In the other extreme, you could assign a different key to each subset you might ever want to broadcast to. This works fine if you care only about a few subsets, but if you want a lot of flexibility then you get too many keys for the users to keep track of. It turns out that there are nontrivial solutions to this problem. The original paper is by Fiat and Naor (in Crypto '93), and searching for "broadcast encryption" online will give tons of follow-up papers offering extensions and improvements.

You might also be interested in "attribute-based encryption", in which each user is associated with a list of different attributes and you can encrypt messages so they can be decrypted by just the users with desired combinations of attributes. This is a somewhat different approach, but it has some beautiful consequences. The original paper is by Sahai and Waters (Eurocrypt 2005), and again there have been many further papers.

This is an interesting question. But it seems to me that in practical cases, you don't encrypt the whole message with the public key of the recipient. Usually, you encrypt it with a fast symmetric algorithm (eg AES) using a random key $K$, and encrypt $K$ with the public key.

The size of $K$ is clearly negligible compared to the size of the message. Hence, if you have to send the same message to several recipients, you just have to encrypt $K$ several time and to append the result to the encrypted message, which doesn't increase its size too much.

Another advantage of this method is that if you want to add a new recipient, you don't have to encrypt the whole message again. Just encrypt $K$ with the public key of your new friend and append the result to the old message.