I just called Apple Support to ask them about switching from Verification to Authentication. They said the sole requirement is the OS you are running. I turned off Two-Step Verification online and once it had gone through, I had the option on my iPhone running 9.3 beta 5 to set up Two-Factor Authentication, which I did.
WARNING! If you do this you will have to re-authenticate all your devices (including Apple Watch from its app). This worked fine except for on my MBA where I had to sign out (deleting Photo Library and iCloud Drive local docs etc.) and sign back in. It wouldn't accept my 6-digit code. I had to restart before it let me back in. Scary stuff for a second but everything is now working again.
On devices not running iOS 9+ or OS X 10.11+ you use your iCloud password and add the 6-digit code to the end each time you sign in.
The benefits of Two-Factor Authentication (as stusgt67 has said) are that it is stronger (6 digit over 4), there are no Trusted Devices (all your devices are act as trusted devices automatically), you can recover your password from Apple Support using personal info such as payment details and history etc. There is also a cool screen showing where a login attempt is being made from.
Overall it seems like a smoother system and probably more future-proof. If you have some spare time and don't mind troubleshooting any issues that arise in the switchover I would recommend it.