The automatic rotation of the iPhone camera has issues sometimes, and you may end up with an awesome video looking like this after you've recorded it.
And while using another app to edit it and save it works, it may end up with it being placed into a different moment, or losing the original meta data from the video.
Thankfully I found a solution!
The iMovie app has an extension. And unbeknownst to me before, you can rotate video with it!
If you select the video you want to edit, you'll see a circle with an ellipsis in the center of it.
Once you tap the iMovie button, you'll see this screen.
It's not super clear, but if you take two fingers, and pinch and rotate them, you'll see this arrow pop up.
Voila! You now have your original video, in all its meta data filled glory. The next step is to just tap "Done".
iMovie will save the video in place (keeping all the original data etc), and your video will be properly horizontal.
The only downside to this is that if your video, like mine, was a slow motion video, you'll no longer be able to edit the points where it's slow. In that type of situation - I would duplicate the original video, and then rotate it using iMovie.