Q:

Same specificity, after taking placement into consideration, :first-letter always wins? 

Take a look at this jsfiddle: http://jsfiddle.net/ZNddz/
.intro:first-letter {
    font-size: 130px;
}
span.letter {
    background-color: red;
    font-size: 30px;
}
p {
    font-size: 80px;
}

The first rule consist of one class selector and one pseudo-element selector = 11
The second rule consist of one class selector .letter and one tag selector span = 11
Both rules have same specificity so it is reasonably to believe that the winner should be the last style.  Obviously it is not the case.  So I decided to add a background-color property to the second rule and as you can see it has a height of 30px. 
I deduce from this that both rule are not selecting the same element.  But it's kinda too bizarre that I want to have an official explanation to this effect. 

A:

I deduce from this that both rule are not selecting the same element. 

This is because .intro is matching the p element whereas span.letter is a descendant of .intro.  As already mentioned, specificity is not relevant when selectors are matching different elements.  But since each selector does match some element, both rules are applied, resulting in your red background taking effect, on span.letter. 

But it's kinda too bizarre that I want to have an official explanation to this effect. 

The spec contains some examples that are very similar to what you have: a block-level element that starts with an inline-level element that contains text, and styles applying to the block-level element, the :first-letter pseudo-element on the block-level element, and its inline-level child.  In all of the examples, the :first-letter pseudo-element is always the innermost descendant in terms of formatting structure; this means that it's nested within the inline-level child element. 
The last example illustrates with a hierarchy of elements including the pseudo-element, although the one just before that contains an overriding rule in its stylesheet, which demonstrates what happens in terms of the cascade:

The following CSS will make a drop cap initial letter span about two lines:
<! DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN">
<HTML>
 <HEAD>
  <TITLE>Drop cap initial letter</TITLE>
  <STYLE type="text/css">
   P              { font-size: 12pt; line-height: 1.2 }
   P::first-letter { font-size: 200%; font-style: italic;
                    font-weight: bold; float: left }
   SPAN           { text-transform: uppercase }
  </STYLE>
 </HEAD>
 <BODY>
  <P><SPAN>The first</SPAN> few words of an article
    in The Economist.</P>
 </BODY>
</HTML>

This example might be formatted as follows:

The fictional tag sequence is:
<P>
<SPAN>
<P::first-letter>
T
</P::first-letter>he first
</SPAN> 
few words of an article in the Economist. 
</P>

Note that the ::first-letter pseudo-element tags abut the content (i.e., the initial character), while the ::first-line pseudo-element start tag is inserted right after the start tag of the block element. 

In your case, both font-size declarations apply as usual, but since .intro:first-letter is nested within span.letter, it uses its own font-size value.  If you used a relative value it would be calculated based on span.letter, and if you didn't include a font-size style at all it would simply inherit it from span.letter. 
Note that the :first-letter pseudo-element does not apply to inline-level elements (it does apply to inline blocks however):

In CSS, the ::first-letter pseudo-element applies to block-like containers such as block, list-item, table-cell, table-caption, and inline-block elements. 

An inline box (one that is generated with display: inline) is not a block container box. ( An example of an inline-level box that is a block container box is an inline-block.) 
If a browser is applying the pseudo-element to an inline, then it's in violation of the spec.  While there's no indication of what should happen when you have a :first-letter rule for both a block container and an inline box descendant, since it does say that it does not apply to inlines, ideally a browser should always ignore the rule targeting the inline box descendant.  Apparently, Chrome thinks otherwise; see Danield's answer.