After all, a lawyer friend of mine argues, a beheading suggests at least some amount of premeditation and deliberation, which is what our criminal law course taught is required for first-degree murder.

The answer is that the first-/second-degree murder line varies a great deal from state to state. Some allow a first-degree murder conviction based on evidence of even a few seconds' worth of premeditation and deliberation. Some require evidence of some time during which the person was calm -- as opposed to in a rage -- and premeditated and deliberated calmly. And some have a detailed list of circumstances that can justify a first-degree murder charge (especially if they use the first-/second-degree murder distinction to distinguish between generally death-penalty-eligible murders and other murders).

New York fits in the last category: New York Penal Law § 125.27 lists thirteen circumstances under which a murder can be charged as a first-degree murder, and it seems likely that none of these circumstances applies here.