> Since I was already using two-step verification, I had to turn it off for the new, two-factor authentication, option to appear.

This can be very confusing and should be made more clear in Apple's documentation the iCloud Preferences UI on OS X.