(David, just to clarify, I easily slide into "lecture" mode...and few of those types of posts end up being...er...brief. So I'm typing to a general audience; not specifically directed to you.)
My first yDNA test was a 12-marker panel back when that was all FTDNA offered. Testing 37 STRs is now considered the entry-level test and, though I'm always a fan of deeper testing (in everything, not just the Y) if money isn't an issue, the 37-marker can still serve informative, important functions.
As with mtDNA, I think that yDNA testing should be done with a purpose in mind. The two types of uniparental DNA don't have the numbers of test-takers that our $59 autosomal tests do, and they can't tell us as much--at face value--about the most recent generations.
That purpose very well could be, "I just want to see if any matches show up." Perfectly valid; but potentially disappointing if close matches are hoped for without underlying hypotheses to check.
As negating evidence (not to be confused with "negative evidence"), a 37-STR test and an HVR1+HVR2 mtDNA test can be quite useful. In other words, if B and C both show descent from A, but that lineage is in question, learning that B and C are of different haplogroups solidly puts the hypothesis to rest: they are patrilineally (or matrilineally) unrelated in anything close to the genealogical timeframe. And in genetic terms, the genealogical timeframe is very recent.
Further, for yDNA, if you're dealing with a fairly mature study with data from multiple participants, it may well be that a 37-marker test plus one or two single SNP results, which can be obtained through FTDNA or YSEQ, is all you need to place you on the correct familial branch even if the MRCAs are not known. My own Williams subproject is an example. There are 36 test-takers in the project now, and if someone unrecruited happens to pop up that's a solid 37-marker match, we can fairly accurately assign him to one of the established branches pending the additional verification of SNPs or more STRs.
It's also important--because so many people have become familiar with autosomal testing--to keep in mind that yDNA really doesn't work in the same way. For one, it can't be as predictive as autosomal testing. By that I mean an ability to pinpoint generational distances and cousinships. Back to 2g-grandparents, the very nature of meiosis and independent assortment give us the ability to form a pretty good guess of the relationship based on the shared autosomal DNA and the number of in-common segments.
Since the Y chromosome never recombines (I'm ignoring the PAR regions because we don't use them for genealogy anyway), its only changes come about via mutation. Even the most volatile STR markers--CDY, DYS710, and DYS712--at their fastest have an average mutation rate of 0.0353...or 27:1 odds that the marker will change at any given birth event. So the number of repeats in any single marker doesn't really tell us anything; it's the variances when looking across a large number of repeat differences that give us any genealogical info.
If the purpose for testing is "to see if any matches show up," definitely start with the 37-marker unless the cost of the Big Y is like, well, lunch money. An unfortunate misconception that sometimes ends up disappointing folks who start with the 37-marker and then upgrade is that more STR markers tested doesn't mean a likelihood of seeing more matches. Generally speaking, if two men aren't a match at 37 markers they won't go on to show as a match if more markers are tested. It can happen--that FTDNA doesn't report someone as a 37-marker match but does at 111 markers--because of the way FTDNA limits what is and isn't shown as a match. But it's fairly rare. For example, if two men are a calculated Genetic Distance of 5 at 37-markers, they aren't considered a match; if those are the only dissimilarities they would then be shown as matches at the 67 and 111 levels because FTDNA's reporting thresholds for those panels are GD7 and GD10, respectively.
Another possible point of frustration can hinge on deep ancestry. Take Scotland as an example. In the Lowlands the use of patronymics gave way to inherited surnames generally during the early part of the 16th century. But it took two more centuries before the Highlands had similarly standardized. Back to our Williams subproject as example, we have six surnames in that "genetic tree," five of which (the sixth is still being researched) have good evidence of not being the result of non-paternal events. Analysis of the various SNP bifurcations indicate the MRCA of all those surname lines lived circa 900 AD, probably in southwest Scotland or northern Wales. Same patrilineal line, different surnames. At 37 markers, I have two GD4 matches shown to men of one of those surnames and we know the MRCA had to have lived between roughly 900 AD and 1100 AD.
Which leads to the last item. Those who come to yDNA testing with a background in looking at autosomal results can misconstrue the yDNA term "genetic distance." With atDNA we typically think of that as a step-wise generational thing, e.g., the generational relationship between 2nd cousins aligning to the shared great-grandparents. With yDNA, it doesn't work that way.
In an oversimplified nutshell, with yDNA "genetic distance" refers to the estimated minimum number of birth events required to display the STR differences shown. And there's no implication there of consecutive birth events. Take a GD of 1. This indicates that there is a difference among the STRs that would have required at least one generation for the mutation to have happened. Doesn't mean it was one generation ago, or even a half-dozen generations ago; evaluating that depends upon the specific STR because the average mutation rates can vary quite a bit. That GD1 could show up between a father and son--but not in the son's brother--or it could have happened with the 5g-grandfather. To make it more complicated, STRs can also perform a circus trick called "back mutation," where, in this example, the son might have a different repeat count at CDY, but the son's son reverts back to the father's count.
A GD of 2 means that two such separate events occurred. And, again depending upon the STRs involved, it's usually highly unlikely that these two independent mutation events happened in the same generation. Ergo, a GD of 2 means I'm not as closely related as I am to the GD1. That's how I can be a GD1 with a known 4th cousin, and a GD4 to someone with a different surname I know I'm not related to until at least 1100 AD...even though the numerals 1 and 4 make it seem like they shouldn't be that far apart.
A final piece of advice: for anyone taking a yDNA test, if you aren't doing it as part of an established hypothesis--like our Williams subproject--it's always a good idea to join one or more of the volunteer-run group projects at FTDNA. There are surname projects as well as projects driven by geography and haplogroup. You can join multiple projects. If an unexpected surname is peppering your Y-37 or Y-111 results, join it. In its matching services, FTDNA doesn't show you the other person's actual STR values. But if all involved have the proper level of preference settings selected, results will be anonymized to the kit numbers and will display the STR values in the group project.