What is the most paranoid way to exchange messages?
RSA is slow to get a decent security... AKA 2048-bit or more.
  


Well, if you want to be ultra-paranoid, then you'll have to accept some trade-offs.  Suffice to say, a one-time 2048-bit RSA key-exchange shouldn't eat up too much processing time.

Using SSL is the most reliable way to exchange information securely; it not only takes care of the key-exchange and message encryption, but also message authentication (ie, man-in-the-middle attacks).

I don't think you should be concerned about AES being 'broken', but if you really want to be ultra-paranoid, you might take a look at using Serpent - it was the runner-up to Rijndael (AES) in the AES contest, with many people considering it more secure, but slower.


  "Serpent was widely viewed as taking a more conservative approach to security than the other AES finalists, opting for a larger security margin: the designers deemed 16 rounds to be sufficient against known types of attack, but specified 32 rounds as insurance against future discoveries in cryptanalysis."