I do not know what your objections are. It's pretty straight forward.

I guess it's something like:

For messages: AES

Key exchange: RSA

Alice and Bob both generates their own RSA keypair (the server do not have their private keys). Alice generates the AES key to be used with Bob, encrypts it using Bobs public RSA key and then sends it to him.. done

It's actually not that straightforward:

- How is the problem of key distribution solved? How does Bob know that the key is in fact Alices and not Mallorys?

- The scheme you propose does not provide forward secrecy.

- (How) is authentication performed? Are signatures used; if so, are they non-repudiable or deniable?

Secure instant messaging is not a solved problem (at least not in the form of a practical, usable implementation).

But then how does Alice know if she's talking to the right Bob and not some evil middle-man? In other words, she has to trust the server that it is giving her the correct public key.

Signing. I.e. Bob encrypts a dummy message or whatever with his private key.

How does Alice get Bobs public key, and how does she verify its authenticity?