I understand as well that you paid a large amount and expect it to be in great condition but since being pretty much screwed by vzw you have these option
return it and get a new one.
get the like new phone and hope it comes with a cover, keep the cover and send the like new phone back.
buy a phone protector/case. I have the otterbox commuter, covers the phone, protects it well and not big of a case as I imagined.
wait for oem covers or replacement covers pop up on sale.
get the oem samsung cover with the screen flip folio thing.
or trade with some body that wont mind.
edit: they have quite a few oem covers on ebay