What signature algorithm do I use?
Answer: RSA.
RSA is great. It’s well understood, and we have padding schemes now (OAEP, PSS) that really work. If you do DH, you can in fact avoid needing to encrypt at all in most protocols, and just do a signing operation. Since PSS is clearly robust against padding attacks (clear even to an uninitiate like me), and OAEP is merely “not yet cracked”, this suggests that signing be preferred where possible to encrypting. The point is, the traditional thorn in RSA is the fear of padding attacks, but hopefully we’re past that now unless you’re sure you need to encrypt something, and even there, RSA is believed to be more than adequate.
Regarding ECDSA
I think DSA is not worth using, and ECDSA is just DSA over a new group. Basically, if your random numbers are even slightly biased, with every signature you leak a tiny bit of information about your private key! Majorly bad. With RSA, you reduce the security of the one connection that used the dodgy random number, but other connections are independent. I think this a deal-breaker for DSA.
I hate to say it, even though ECDSA is faster than RSA for most operations, you should consider it obsolete junk (in a modern package) unless you’re very careful.
For ephemeral keys it’s OK, but you don’t normally sign using ephemeral keys. There’s one application of this though: using an existing secure connection to bootstrap another. In this case, you can make an ephemeral key, exchange it over the side-channel, then the peer can authenticate you using it. Make sure you only ever use it once, and you’re OK, you don’t need to worry whether someone has ever used the key before for another purpose. In this scenario, the ECDSA key is a slightly more expensive, but much more comforting, form of shared-secret authentication.
Lattice methods
One day, we’ll replace RSA with something else. Lattices methods seem to be the most promising way forward: the underlying problem is clearly not easy, and is thought to be resistant to quantum cryptography. Unfortunately, this is the only cryptographic primitive where I don’t have the background to read the underlying results, but my gut feeling is that we’ll get a widely-recognised good lattice signature scheme fairly soon.
NTRUSign, the most popular one so far, is moderately convincing to me, but it has some difficulties. I expect it’s likely to be cracked eventually (that is, be found to have a good few powers of two knocked off its security; “broken” doesn’t necessarily refer to having a practical attack exists). I think we need to wait for twenty years before using these sorts of things in production, although the company that has the NTRU patent is desperately trying to get people to buy!