OK, I finally figured it out. I feel like this probably isn't the way it's supposed to work and I had to dig around the source code of ServiceAccountCredential, but it works. I actually have this split out a bit, but for the sake of clarity here it is altogether.
I also switched from Google.Apis.Authentication to Google.Apis.Auth.
public static Feed<Contact> MakeRequest(string userId, int numberToRetrieve = 9999)
{
var serviceCredential = new ServiceAccountCredential(new ServiceAccountCredential.Initializer(ServiceEmail)
{
Scopes = new[] { @"https://www.google.com/m8/feeds/" },
User = userId,
}.FromCertificate(Certificate));
var reqAccessTokenInfo = serviceCredential.GetType()
.GetMethod("RequestAccessToken", BindingFlags.Instance | BindingFlags.NonPublic);
var task = (Task<bool>) reqAccessTokenInfo.Invoke(serviceCredential, parameters: new object[] {new CancellationToken()});
task.Wait();
var settings = new RequestSettings(Properties.Settings.Default.ApplicationName, serviceCredential.Token.AccessToken);
var cRequest = new ContactsRequest(settings);
var query = new ContactsQuery(ContactsQuery.CreateContactsUri(userId)) { NumberToRetrieve = numberToRetrieve };
return cRequest.Get<Contact>(query);
}