SSH key-type, rsa, dsa, ecdsa, are there easy answers for which to choose when?

In practice, a RSA key will work everywhere. ECDSA support is newer, so some old client or server may have trouble with ECDSA keys. A DSA key used to work everywhere, as per the SSH standard (RFC 4251 and subsequent), but this changed recently: OpenSSH 7.0 and higher no longer accept DSA keys by default.

ECDSA is computationally lighter, but you'll need a really small client or server (say 50 MHz embedded ARM processor) to notice the difference.

Right now, there is no security-related reason to prefer one type over any other, assuming large enough keys (2048 bits for RSA or DSA, 256 bits for ECDSA); key size is specified with the -b parameter. However, some ssh-keygen versions may reject DSA keys of size other than 1024 bits, which is currently unbroken, but arguably not as robust as could be wished for. So, if you indulge in some slight paranoia, you might prefer RSA.

To sum up, do ssh-keygen -t rsa -b 2048 and you will be happy.

As gilles says DSA is risky because if you make signatures (and using your key with a ssh client to log in is effectively making signatures) on a box with a bad RNG your key can be compromised. AIUI this made Debian basically abandon DSA for keys used on their infrastructure in light of the Debian OpenSSL random number generator fiasco.

http://meyering.net/nuke-your-DSA-keys/

ECDSA is relatively new, from some quick searching it seems it was introduced in 5.7. Afaict most of these systems are out of support and should probably be migrated but we all know that doesn't happen somtimes. For example, Debian squeeze and ubuntu lucid. ECDSA has advantages in that a key can be much smaller than a RSA or DSA key for the same level of (presumed) security. Unfortunately it shares the disadvantage of DSA of being sensitive to bad random number generators. There are also concerns that the elliptic curves traditionally used may have been backdoored.

ED25519 is an even newer option, introduced by openssh 6.5. It is a variant of the ECDSA algorithm but it solves the random number generator problem and uses a "nothing up my sleeve" curve. It will probably be the best option in the long term but right now there are still supported systems out there that don't have sufficiently new openssh.

So IMO that makes RSA (with a 2048 or 4096 bit key depending on how paranoid you are) still the most reasonable choice for general use.

Edit: update to current situation as of March 2017.

DSA and ECDSA have fixed length keys, and they are US government standards meaning that they know more about the standards than the general public. RSA is better known and you can generate longer keys with it (default is 2048 as opposed to DSA's 1024 bit fixed length), so it is (arguably) better to use.