How to test any features that require authentication?
As mentioned in my question, it was pretty clear that Behat was failing to login, so I began to look for modules that might interfere with the login process. 

It turns out that we are using the module AntiBot (https://www.drupal.org/project/antibot) and when we disabled this module, we were able to run tests that involved successfully logging into Drupal.