The key is in the previous step of the SalesForce SOAP API Quick Start.
You can add either a .NET 2.0 style Web reference, or a .NET 3.0 style Service reference, depending on your version of Visual Studio and preferred developer environment. A .NET 3.0 style reference uses services like SoapClient instead of SforceService. (emphasis mine)
The following section of that page details adding a web reference, but offers no guidance for adding a service reference. It's even easier than adding a web reference.
1. Generate Your WDSL
Browse to your Salesforce.com instance and generate a WSDL file (same as in the Salesforce docs).

2. Add a Service Reference
I'm using Visual Studio 2017. This is what the process looks like for me.

Note that I had to set the namespace to "sForce".

3. Add a Using Statement
The namespace of the Salesforce reference is placed inside the project reference. As you can see, there's no compile error for my reference to SoapClient, which was provided in the sForce namespace.

Since the documentation gives example code for the newer service reference, it should really include instructions to set up the service reference. But hey, they're pretty good docs overall, so I guess it's fine.
Do note that there's a performance impact to using the service instead of the web reference.
Also note I had to use a workaround to avoid a bug in how the reference is generated from WSDL. It's described quite well in another answer.
4. Use the Service
Once the service is set up, you can use code from the Salesforce tutorial to log in (copied here with slight modifications):
public class SfSession
{
public static SoapClient client;
private static SoapClient loginClient;
private static SessionHeader sessionHeader;
private static EndpointAddress endpoint;
public bool Login()
{
string username = "<EMAIL>";
string password = "<PASSWORD>(<TOKEN>)";
loginClient = new SoapClient();
ServicePointManager.SecurityProtocol = SecurityProtocolType.Tls12;
LoginResult lr = loginClient.login(null, username, password);
endpoint = new EndpointAddress(lr.serverUrl);
sessionHeader = new SessionHeader
{
sessionId = lr.sessionId
};
client = new SoapClient("Soap", endpoint);
return true;
}
private void Logout()
{
client.logout(sessionHeader);
}
}
(btw, don't leave your username/password in code... I put it there solely for testing)
Microsoft.Web.Services3.Messaging
. Instead they are referencing the different output between adding a Web Reference and a Service Reference. – Daniel Ballinger Jan 24 '17 at 20:32