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.
Another thing to take into account is that generating large number of distinct RSA keys can be done quite rapidly, and even more so if the attacker doesn't care if the keys are actually secure.
For example, consider an RSA key of the form:
Key = [32 bit prime] * [992 bit number of known factorization]
Each 32 bit prime results in a distinct key, even if we keep the larger number constant. So, we create the 992-bit numbers, and for each such number, scan through a list of precomputed 32 bit primes, and then spin off keys by doing a single 32x992 multiply and computing the hash of the resulting certificate. Doing this can plausibly result in our generating one million plausible looking certificates and their fingerprints per second on a single CPU.
Hence, if we assume that an attacker has access to 10,000 such CPUs for a year, he could scan through about $2^{58}$ such certificates looking for a partial hash match.
And yes, this idea can be modified to be usable as a Rainbow table, should the attacker prefer not to redo all this computation for every certificate he wants to MITM.
The result of this argument means that, while CodeInChaos's advice is conservative, it isn't ridiculous. I certainly wouldn't go much below 80 bits (especially since the above computations are for today's computers; not the ones we'll have next decade); a few more than that would certainly be prudent.
There are no collision attacks, only multi-target pre-images. I generally recommend 160 bits in such a scenario(justified by a 128 bit security level with $2^{32}$ interesting targets for the attacker), and that's a rather conservative choice.
Stopping after 160 is plenty. TOR onion addresses have similar properties, but only 80 bits, and I've heard of no successful pre-image attack against those. So even if you verify only 80 bits, I wouldn't worry much.
