Try the easy way first: under Prefs:Sharing:Internet Sharing, enable some sort of Internet sharing, e.g., Wifi to Bluetooth PAN. Disable. See if things work. (Based on my postmortem, this probably would have fixed the specific problem that I encountered.)

I followed the basic instructions under the “Reset the Network Configuration Files” heading of this article, but with some variations because I found some other junk in the same folder. Here’s my best reconstruction of what I did at the Terminal. Since this could potentially break things, don’t do this unless you’re experienced with editing your system files!

• Close everything else, save, make sure your backups are up to date, etc.
• Go to /Library/Preferences/SystemConfiguration.
• Make a backup directory, say, ~/prefs-sysconfig-backup
• Using sudo, move all files in SystemConfiguration to your backup directory. (This will fail for com.apple.Boot.plist but everything else should work fine.)
• Reboot. The files should be recreated automatically.

Looking at the diffs, I suspect that my problem was actually caused by com.apple.nat.plist referring to a PrimaryInterface that no longer existed. The suspicious entry looked like:

        <key>PrimaryInterface</key>
        <dict>
            <key>Device</key>
            <string>lo0</string>
            <key>Enabled</key>
            <integer>0</integer>
            <key>HardwareKey</key>
            <string></string>
            <key>PrimaryUserReadable</key>
            <string>FakeNet</string>
        </dict>