I definitely recommend getting all of your contacts together in one place as well! I prefer to back them up to Google, because then if I add someone's email address down the road and have to send them something, it's already in my gmail if I'm on my computer instead of my phone or tablet.
VZW's is probably the best second option, just because it's not OEM dependent. I remember one of my old Moto phones used to ask me whether I wanted to save a contact to Google or whatever Moto's option was...every time I added one. No matter how many times I told it "Always do this."
Anyway, I lost some contacts when I switched to a different manufacturer's phone. When they post properly to Google, it's just a matter of signing in with your account when you get a new phone and they're all there. It can be a bit tedious to get them all gathered together/transferred to one place, but it's definitely worth it in the long run.
NOW
On to your question about pictures. Anything shown in Photos, I believe, is actually what's been uploaded to your Google+ account. Photos is currently tied directly to G+ (there are talks of separating them). Those that you've taken recently (with your current device) should be stored on the phone somewhere, but those and the rest are likely in the cloud. (Unless, of course, I'm mistaken and you never allowed your photos to be backed up. Then, they should all be on the device somewhere.