After hours of frustration, I finally got it to work. I forget what EXACTLY I did, but this could be the gist of it. First I set my iMessage "Start new conversations from" to the SAME email. Then, I tried to pair my phone and MBP from the Menu Bar icon, and it connected (click on the icon, then click on your iPhone in the list, then click "connect to network"). After that, I opened the iMessage settings on my phone, went to Text Message Forwarding, then toggled my MBP to "on". My phone then asked for the code, which my MBP supplied a minute later. Then, once they were connected, Handoff and SMS Relay worked like a charm (except for finding non-iOS friends to test-spam this with, it is rather hard sometimes, but I was able to find one). After all of this, I changed my "start new conversations from" back to my phone number and it still worked!
NOTE: I was riding in a car (NOT driving lol) while doing this, so I was using a Personal Hotspot from my phone that I set up manually. When using Handoff, the blue Hotspot bar at the top of my iPhone said that it had two connections, not one like it usually does. I checked, and nobody in the car was on it, and I don't think that someone was tailgating me and broke into my Personal Hotspot. Perhaps this is a bug, or it offers some insight as how this works.
EDIT: Now that I am in a building with WiFi, my iPhone does not want to connect to my MBP via Bluetooth. When I switch in my Personal Hotspot, then the iPhone and MBP connect just fine and Handoff and SMS Relay work. Albeit this is not my home network, so they may have blocked some of the stuff here. I'll have to test it on my home network later and update this.