First, be careful what you assume, and verify that it's true. Your description leaves considerable room for doubt that your assumptions are correct.
Second, to make a switched outlet always on, you simply move the wire feeding the outlet from the switched side of the switch to join with the always-hot side of the switch. That can be "remove the switch and replace it with a wire-nut" but since it sounds like you want the switch to keep working for the fan, and you want to add another switch, it's more likely that you may need a pigtail at the "always hot" wire to connect the (formerly switched) outlet and switch to always-hot, and possibly an additional switch to always-hot as well.
An alternative layout for your cables that appears more in line with what you describe as the function (fan and light are switched, so we expect TWO connections on the "switched" side and ONE connection on the "always-hot side") is that power comes from the panel to the fan location, and from the fan to the switch location on the red wire (which you state goes alone to one side of the switch), and is switched to go back to the fan on the black wire in the same cable, and on to the outlet in the other cable's black wire (since you state two black wires are connected to the other side of the switch.)
You would disambiguate and remove assumptions by determining which wire is actually Always-Hot via turn off, disconnect & isolate, turn on and see what is affected. There could be things going on in junction boxes you haven't opened or described that might make this guess at your layout incorrect, so verify before proceeding as if it was true.