What I know about the different types of SSH keys (and some opinions)
Modern versions of SSH support up to four different types of SSH keys (both for host keys to identify servers and for personal keys): RSA, DSA, ECDSA, and as of OpenSSH 6.5 we have ED25519 keys as well. Both ECDSA and ED25519 uses elliptic curve cryptography, DSA uses finite fields, and RSA is based on integer factorization. EC cryptography is said to have a number of advantages, particularly in that it uses smaller key sizes (and thus needs smaller exchanges on the wire to pass public keys back and forth).
(One discussion of this is this cloudflare blog post.)
RSA and DSA keys are supported by all SSH implementations (well, all SSH v2 implementations which is in practice 'all implementations' these days). ECDSA keys are supported primarily by reasonably recent versions of OpenSSH (from OpenSSH 5.7 onwards); they may not be in other versions, such as the SSH that you find on Solaris and OmniOS or on a Red Hat Enterprise 5 machine. ED25519 is only supported in OpenSSH 6.5 and later, which right now is very recent; of our main machines, only the Ubuntu 14.04 ones have it (especially note that it's not supported by the RHEL 7/CentOS 7 version of OpenSSH).
(I think ED25519 is also supported on Debian test (but not stable) and on up to date current FreeBSD and OpenBSD versions.)
SSH servers can offer multiple host keys in different key types
(this is controlled by what
HostKey files you have configured).
The order that OpenSSH clients will try host keys in is controlled
by two things: the setting of
HostKeyAlgorithms (see '
ssh_config' for the default) and what host keys are already known
for the target host. If no host keys are known, I believe that the
current order is order is ECDSA, ED25519, RSA, and then DSA; once
there are known keys, they're tried first. What this really means
is that for an otherwise unknown host you will be prompted to save
the first of these key types that the host has and thereafter the
host will be verified against it. If you already know an 'inferior'
key (eg a RSA key when the host also advertises an ECDSA key), you
will verify the host against the key you know and, as far as I can
tell, not even save its 'better' key in
(If you have a mixture of SSH client versions, people can wind up
with a real mixture of your server key types in their
files or equivalent. This may mean that you need to preserve and
restore multiple types of SSH host keys over server reinstalls, and
probably add saving and restoring ED25519 keys when you start adding
Ubuntu 14.04 servers to your mix.)
In terms of which key type is 'better', some people distrust ECDSA because the elliptic curve parameters are magic numbers from NIST and so could have secret backdoors, as appears to be all but certain for another NIST elliptic curve based cryptography standard (see also and also and more). I reflexively dislike both DSA and ECDSA because DSA implementation mistakes can be explosively fatal, as in 'trivially disclose your private keys'. While ED25519 also uses DSA it takes specific steps to avoid at least some of the explosive failures of plain DSA and ECDSA, failures that have led to eg the compromise of Sony's Playstation 3 signing keys.
(RFC 6979 discusses how to avoid this particular problem for DSA and ECDSA but it's not clear to me if OpenSSH implements it. I would assume not until explicitly stated otherwise.)
As a result of all of this I believe that the conservative choice is to advertise and use only RSA keys (both host keys and personal keys) with good bit sizes. The slightly daring choice is to use ED25519 when you have it available. I would not use either ECDSA or DSA although I wouldn't go out of my way to disable server ECDSA or DSA host keys except in a very high security environment.
(I call ED25519 'slightly daring' only because I don't believe it's undergone as much outside scrutiny as RSA, and I could be wrong about that. See here and here for a discussion of ECC and ED25519 security properties and general security issues. ED25519 is part of Dan Bernstein's work and in general he has a pretty good reputation on these issues. Certainly the OpenSSH people were willing to adopt it.)
PS: If you want to have your eyebrows raised about the choice of elliptic curve parameters, see here.
PPS: I don't know what types of keys non-Unix SSH clients support over and above basic RSA and DSA support. Some casual Internet searches suggest that PuTTY doesn't support ECDSA yet, for example. And even some Unix software may have difficulties; for example, currently GNOME Keyring apparently doesn't support ECDSA keys (via archlinux).