What's stopping a carrier from simply E2EE everything from Verizon, and then using Verizon to transfer the data?
Nothing, if you're talking about using them as an internet connection. You're describing Signal and other E2EE applications, basically. If you're talking about SMS and traditional phone calls, no, those protocols don't support encryption because they're not built to. You can jury-rig it which I'll get to later, but otherwise, it's just not possible due to the tech.
the encrypted data could still be collected and sold, but it wouldn't matter if the encryption was setup properly, right?
Correct, as all they'd see is gibberish with no way to decrypt it.
if carriers simply don't support E2EE, couldn't carrier locked phones install the software (since most install software anyways) required to make E2EE work?
Yes, but not with "phone" functions like SMS and PSTN (Public Switched Telephone Network) calls. SMS character limits are arbitrary and make it impossible to encrypt content in a single message. Signal, back in the Text secure days, used to use MMS to carry encrypted text, or where MMS wasn't available they'd send encrypted chunks and decrypt in the app on the other end. There's a reason they stopped doing that, and a reason it's a rare feature in messaging apps: it's hard to build and maintain and have it be reliable.
PSTN, I don't know of any way to encrypt the call. Edit: Actually I guess over a traditional copper wire you could encrypt a voice call with an eletronic device that could encode your speech into audio, so it’d sound like a dial-up modem if you listened to it, and only another device with the decryption key could decode the audio back into speech, but there’d probably be some delay and I don’t even know if that’d be legal or allowed by the carrier’s TOS. We're still extending bits of the PATRIOT Act, right?