I'm on Verizon also. I have the Galaxy S5 with OS 5.0. Found it in the Google Play Store but it said it is not compatible with my phone. But if you read about it.....it states......
"The 4th version of Samsung Internet brings lots of new and exciting features.
This update is available for Galaxy S7 Edge, S7, Note5, S6 Edge+, S6 Edge, S6, S6 Active, Note4, S5, S5 Neo, S5 Active, S5 Sports, S5 LTE A, Note3, S4, S4 Duos, S4 Active, S4 LTE A, A7, A8, A5x, A7x, and A9x with Android 5.0 and above."
The S5 is listed! This really sucks!!
EDIT: I just signed in with another account on my S5 for the Google Play Store and NOW I was able to download it. Weird.....really weird. Will check the browser out and see how I like it.