Backup assistant is your easiest bet. This used to cost money, but Verizon waived all fees associated with it. I believe this is what they would call "going the extra mile" because it doesn't require a working previous phone to work, and it's something they used to get Data and monthly charges from.
Some stores still do contact transfers, though most that do will charge for it. The reason behind this is because contact transfers, specifically if the phone is a bit worse for wear, can take quite a bit of a reps time, and if you want pictures transfered, it can literally take over an hour until everything is done (and most stores only have 1-2 machines because they are insanely expensive to purchase and maintain). The problem (especially for retailers) is that customers are increasingly coming to the store only when they have issues with devices they bought online, and stores can't afford to keep their doors open on customer service alone.
Newer verizon android phones ship with Backup assistant. But even if you get a phone that doesn't have it, you can still go online and export your contacts into a format google should be able to read and put on your phone.