I wouldn't buy a USB-C to 3.5mm adapter without making absolutely certain that it is compatible with the particular phone. Although there is a USB-C audio standard it doesn't seem that all of the manufacturers are implementing it properly, because these adapters often don't work with different phones.
As for why they all have a cable, probably because it would be quite a long rigid stick coming out of the bottom otherwise. These things are active components: they contain a small circuit board with a DAC and amplifier on it, the audio components that have been removed from the phone (since the phone is only outputting digital audio and these things are to convert that to an analogue signal for your headphones), so it can't be shrunken down to just the jack itself sticking out of the phone.
I'm afraid I don't know what Verizon offers (not American), so can't advise on that. The new Sony's do, but Sony phones aren't big in the US so I don't know whether VZW will carry them. LG and Samsung still have it, but their recent announcements are phablets (of course their smaller phones from earlier this year are still available) At this moment in time it's actually only Motorola and HTC who have removed it, plus newbies Essential and a pretty strong rumour that the next Pixels will also lack it. The rest of the big Android manufacturers still have it (and probably lower-end phones from some of those I've named still do too). How that will look in a year's time is harder to guess.
