You didn't have the Find My iPhone app installed? Or Find My Friends?
If not bummer, definitely install on your new one.
As for the insurance, Verizon uses a third party for the insurance so it's not technically Verizon that is handling the situation and there is really nothing you can do to speed up the process. I've been through it before, a few years ago. I was told by Verizon it's out of their hands since they go through a third party. I believe the company is called Asurion and yes, they will be sending you a refurbished iPhone and you don't have much choice either. My wife had a pink Blackberry that needed to be replaced and they stated they cannot guarantee what color would be sent out and she received a black refurbished device.
Good luck