How many bits of hash are realistically needed for key verification? Say I'm connecting to a web server secured with TLS but with a self-signed certificate. Accordingly, I call the owners of the server and ask them what SHA1 fingerprint they have.

They start reading out the hex digits to me and I follow along, but before reaching the end, I just say "That's fine thanks, no need to read the rest." as I click the OK button.

How far along is the point where its reasonable to stop checking and still remain practically secure?
I recommend stopping after 20 hex digits, i.e., 80 bits.  That should be enough for security.  Suppose you connect to no more than 128 different servers with self-signed certificates, for which you will use this verification procedure.  Then it would take an adversary $2^{80}/128 \approx 2^{73}$ steps of computation to fool you, which is beyond what is feasible given the current state of technology.

I would not recommend 40 hex digits, i.e., 160 bits.  That offers needlessly poor usability.  If there's one thing we've learned about usable security, it is this: If it's not usable, it won't be secure either.  That's because people will find excuses to avoid the security advice, or to completely evade your security mechanism, or skip the verification step.  Or, they'll be tempted to communicate in the clear and skip the crypto and they'll make up rationalizations for it ("oh, this conversation isn't very secret", "oh, just this once", "what are the odds someone is listening in?", "I'll use coded references and it'll probably be OK"), and historically speaking, that tends to turn out badly.

As @CodesInChaos correctly states, collision attacks are not an issue here, so you don't need to double the number of bits you check.  Therefore, there is no need to check 160 bits.  Instead, as @CodesInChaos explains, this is a multi-target pre-image problem.  In general, if you want to force the attacker to perform $2^b$ steps of operation, and if you connect to $n$ different servers that use self-signed certificates that you verify in this way, then you should verify $b + \lg n$ bits of the hash.  I would suggest using a value of $b$ somewhere in the range 64..80; $b=80$ should be more than sufficient (a conservative choice), and $b=64$ is probably adequate.

I checked my SSH ~/.ssh/known_hosts file, which records all of the SSH hosts I've connected to in the past decade or so.  I found about 117 different hostnames, corresponding to $n=79$ different public keys (sometimes one host has two slightly different hostnames).  So taking $n=128$ seems like a pretty reasonable, conservative choice.

Note that you're not going to get perfect security through this mechanism.  All you need to do is make the MITM attack expensive.  In real life, rather than spending millions of dollars to find a matching public key through some expensive computation, it is more likely that the bad guy will attack some other weaker point in your system (e.g., exploit a zero-day in your software or in the server's software; bribe or impersonate the owner of the server; etc.).  Therefore, realistically, 18 hex digits (72 bits; i.e., 65 bits of security, assuming you connect to no more than 128 such servers) is probably enough to ensure that the crypto is not the weakest link in the system, if you want to cut it fine.  But 20 hex digits gives you a little bit of a margin for error.

If you want to optimize this to the max, you could use a slow hash function (e.g., bcrypt, PBKDF2), which might slightly reduce the number of digits you need to verify.  For instance, if you use 4096 iterations of hashing, you can probably reduce the number of hash digits to check by 3 hex digits (since $4096=2^{12}$, and 12 bits = 3 hex digits).  Also, if your hashing procedure hashed both the public key and the domain name (rather than just the public key), you could eliminate the opportunity for multi-target attacks, reducing the number of bits you need to verify from $b+\lg n$ to $b$ bits (e.g., reducing the number of bits to verify by about 7 bits, or about 2 hex digits).  You could also look at Paŭlo Ebermann♦'s suggestions for how to encode the hash in a way that makes it easier to compare hashes.  For instance, a sequence of words may be easier to verify than a sequence of hex digits, particularly if the dictionary is chosen appropriately.