What is a good general purpose GnuPG key setup?

About Using Subkeys

Use one primary key for each identity you need, otherwise, use subkeys.

Examples for using multiple primary keys:

You don't want to mix up your private and professional keys
You need some key not connected with your "real life" identity, eg. when prosecuted by the authorities

Examples for using subkeys:

You want to use multiple keys for multiple devices (so you won't have to revoke your computer's key if you lose your mobile)
You want to switch keys regularly (eg., every some years) without losing your reputation in the Web of Trust

I recently posted about How many OpenPGP keys to make in another answer.

About Key Sizes

The GnuPG developers recommend using 2k RSA keys for both encryption and signing. This will be definitely fine for currently used subkeys.

As your primary key will not be used for anything but keysigning and validating signatures (and revocation of course), it is seen as good practice to have a quite huge key here, while using smaller sizes (huge enough for time you will need them) for subkeys (which will speed up calculations and reduce file sizes).

I had a more detailed answer facing RSA with DSA/Elgamal for another question at Superuser, go there for reading further.

Key Expiration

There are two ways a private key could get compromised:

Somebody is able to steal it from you
Somebody is able to recalculate it from your public key

First is a matter of your computer's security (and how you use your key, read below), second is a matter of time. Today (and probably the next few years), RSA 2k keys will be totally fine. But computing power rises dramatically, so an attacker needs less CPU cores/graphic cards/computers/power plants to recalculate your private key. Also, glitches could be found in the used algorithms, leading to much less computing power needed. Quantum computers could speed up things even more.

A key expiration date will limit the validity of your key to a given time you expect it to be secure. Any attacker cracking it afterwards will only be able to read encrypted data send to you, but nobody will use it any more; if an attacker gets hold of your key and you stay unnoticed, at least it will stop him from having use from it after a given time.

Expiring your primary key will let you lose all your Web of Trust reputation, but at least invalidates your key after a given time if you lose access (what should never ever happen, read on at the end of my answer).

Storing your Primary Key Offline

Your primary key is the most crucial one. All trust - both incoming and outgoing - is connected with this. If somebody gets access to it, he's able to:

Create new keys using your name (and GnuPG always uses your newest subkey by default!)
Revoking subkeys and primary keys
Issuing trust to other keys, which is the worst thing to happen: An attacker could create a new key, giving it trust from your old one and then revoke your old key, leaving you without any access to your "moved" identity - he's literally overtaking your identity.

How important is it actually to keep the certification key offline when one uses a) a "really" strong passphrase [...]?

Your computer always could be hacked or infected by some malware downloading your keys and installing a key logger to fetch your password (and this is not a matter of which operating system you use, all of them include severe security holes nobody knows about at this time).

Keeping your primary (private) key offline is a good choice preventing these problems. It includes some hassles, but reduces risks as stated above.

Highest security would of course mean to use a separate, offline computer (hardware, no virtual machine!) to do all the key management using your primary key and only transferring OpenPGP data (foreign keys and signatures you issued) using some thumb drive.

b) a hardware device like an OpenPGP card?

OpenPGP smart cards are somewhere in between storing it offline on a thumbdrive, but attaching it to your computer for signing and using another offline computer dedicated to this purpose. Your private key will never leave the smart card (except for backup purpose) which requires an "admin PIN", all signing and even key creation will happen inside the card. "Using" your key (encryption, signing, giving trust) will only require a "user PIN", so even if you connect the card to a "harmed" computer, the attacker will not be able to completely overtake your ID.

You can store your public key wherever you want, for having real use of OpenPGP, you even should send it (and your other public keys) to the keyservers.

And do not forget to create and print a revocation certificate of your primary key. Losing your private key not having this certificate means there is a key you cannot access any more lingering on the keyservers and you can't do anything about it.

Print it, possibly several times, and put it to places you trust. Your parents, some bank deposit box, ... - if this certificate leaks, worst thing to happen is losing your Web of Trust.

Key expiration makes sense only if you can predict a point in time where the key will cease to be secure, due to advances in Science, technology, or lack of interest on your part with regards to protection of the private key. Whether a given asymmetric key will become weak in the future depends on estimates on future increase of computational power (which is only fuzzily predictable) and new scientific findings (which are not predictable at all). For computational power, various researchers and institutional bodies have published recommendations with predictive equations; see this site for a good survey. Remember that while a good deal of Science and informed guesses have gone into these recommendations, their predictive success rate is not necessarily better than if they had slaughtered a sheep and looked at its liver to unravel the will of the gods.

Anyway, the usual assumption is that 2048-bit RSA keys should hold the line up to at least year 2030, and probably longer, under the following conditions:

The key was properly generated with a cryptographically secure PRNG. (GnuPG is believed to use the OS resources properly, but so was OpenSSL until that time when Debian goofed spectacularly).
No mathematician finds a deadly shortcut to integer factorization (last major advance was the discovery of the General Number Field Sieve in 1989; since then, research has focused on a lot of small, cumulative optimizations; current record is 768 bits).
Computers keep on running under the physical laws as we know them, and, in particular, quantum computers keep on being theoretical only (a few QC were built, but the current record seems to be the factorization of an 8-bit integer).

While any of these conditions may fail in the future, the time of failure cannot be predicted with any kind of accuracy, so you cannot design your key expiration policy around them. The best you can do is to suppose that they won't occur, and pray for the best.

DSA and ElGamal keys offer similar resistance for the same key lengths; i.e. 2048 bits for these should be fine, too.

On a more practical point of view, you should keep your expiration dates before year 2038.

Your master key should be kept mostly offline. If your master key is protected by a really strong pass phrase, then it can be stored anywhere, in particular in an online computer. But when you type that pass phrase, you have to be sure that the machine you are using at that time is "clean" and not riddled with keyloggers and other nefarious add-ons. The master key is "important" (at least for you), and you really do not want to see it stolen. A computer which is "online" and has been involved in daily Internet-related activities cannot be considered to be clean with 100% guarantee.

So storage on your computer, smartphone, Gmail account... is fine, as long as usage is on a dedicated offline computer. You should use your master key only to emit sub-keys, i.e. once in a decade at most. This raises the additional issue of the pass phrase: how will you remember a pass phrase that you never type, ten years from now ?

For really good resilience, I suggest printing the master key file (Base64-encoded), then writing the passphrase with a pencil (do not use your printer for that !) on the same paper, and storing that in a bank safe. At worst, if ten years from now you lost the file and forgot the pass phrase, you can still type it in and recover your master key.

Cookbook

This is a cookbook approach which exemplifies the nice answer above. It is a distilled version of Generating More Secure GPG Keys: A Step-by-Step Guide which separates all those functions into separate keys

Create primary key

$ gpg --expert --gen-key

(8) RSA (set your own capabilities)

Your selection? 8

(S) Toggle the sign capability

Your selection? s

(E) Toggle the encrypt capability

Your selection? e

(Q) Finished

Your selection? q

What keysize do you want? (2048) 4096
Key is valid for? (0) 3y
Is this correct? (y/N)y

next add UID, email and passphrase.

This generates a certify-only primary key.

Create signing (etc.) subkeys

$ gpg --expert --edit-key [email protected]
gpg> addkey

(8) RSA (set your own capabilities)

Your selection? 8
Your selection? e
Your selection? q

What keysize do you want? (2048) 3072
Key is valid for? (0) 6m
Is this correct? (y/N)y
Really create? (y/N) y

This generates a sign-only subkey.

(Repeat this addkey process for the Encryption and Authentication subkeys)

[...]

When we’re finished, we’ll save the key to our keyring.

gpg> save

Backup

$ gpg -a --export-secret-key [email protected] > secret_key
$ gpg -a --gen-revoke [email protected] > revocation_cert.gpg

Removing the Primary Key

$ gpg -a --export-secret-subkeys [email protected] > secret_subkeys.gpg
$ gpg --delete-secret-keys [email protected]
Delete this key from the keyring? (y/N) y
This is a secret key! - really delete? (y/N) y
$ gpg --import secret_subkeys.gpg

This leaves them in a "laptop" state with the primary secret key missing. Transfer is done via

$ gpg -a --export-secret-keys [email protected] > laptop_keys_secret.gpg
$ gpg -a --export [email protected] > laptop_keys_public.gpg

(transfer via USB-Stick or CD) and on the laptop

$ gpg --import laptop_keys_public.gpg
$ gpg --import laptop_keys_secret.gpg