Funny, we just did the same thing. Upgraded (I like how you put that) from Sprint to AT&T and my wife went from a Viper to the S4 Active. She can't believe the difference either.
As far as the voicemail, there is a voicemail button on the phone dialer keypad (bottom left, pic of a cassette). AT&T also uses their own "My Messages" app, it combines sms, call log & voicemail into 1 app. I haven't tried it & if you read the reviews in the Play Store, it seems to suck due to recent updates.