It is quite interesting how not only the answers, in varying degrees, drift off-topic, but also how the question and or the premise conditions are clearly misunderstood at times, with responses that are unrelated to the question! Several aspects of the answers provided are excellent, but don't quite get to solving Matthew's dilemma. Yes, this is very late in the game, as in four years late! But I just tripped over it and thought others may also find it who have a similar situation and are looking for a useful answer.
First off, Matthew's accompanying diagrams throw a potential respondent off track if not considered only as representative of his situation. He said, "we have 2 different duplex outlets on opposite sides of the room", and, "Both outlets are switched. Switch goes on, both outlets get power. Switch goes off, both outlets lose power." Ok, now we know that neither outlet is half-switched, as one respondent suggested; both outlets are fully switched -- power on, or power off. Next, he said, "I am trying to add a second switch into the same box that will be connected to a ceiling fan."
And he said, "The second [option] would require tearing down plaster through a good part of my wife's studio and more patching than I think we're really able to do right now."
With that information we can provide a plausible and effective answer. His primary question is should he wire a new 3-wire cable in place of one or more of the existing 2-wire cables between the two existing outlets and up to the switch box. Answer: yes, but only if you want to maintain the switched outlets. Although he never said whether or not he wanted to do that, he did imply it by saying, "I am trying to add a second switch into the same box that will be connected to a ceiling fan."
This is where a bit of experiential intuition comes in handy. He wants to install just a ceiling fan, switched from the wall; in fact, from the same existing 1-gang switch box, as also implied by the information he provided. Given the conditions, and the fact that he does not want to engage in all the work necessary to run the total of three new 3-wire cable(s) (or add a second switch), and have to do all the plaster repairs, we can suggest the following.
Turn off the power; open up the two duplex outlets and the switch outlet; remove the switch; reconfigure the wiring at both duplex outlets such that both duplex outlets are no longer switched, rather, wired to be live all the time. This means simply connecting the two whites to the neutral side and the two blacks to the hot side of each of the two duplex and close them up.
Now the black at the switch box is a full-time, live hot wire, and the white at the switch is a "live" neutral wire.
Next, buy a light kit for the ceiling fan. Next, wire a new 3-wire up to the ceiling fan/light location from the existing switch box. Of course, install a fan-rated box support assembly. And of course, connect/splice/terminate the EGC (Equipment Grounding Conductor), the bare copper wires, to the duplexes and the boxes and the switch, as and where required.
At the switch box, using a new duplex switch (two single pole switches on one device yoke, a "stacker" as it is sometimes called), connect the wires: first, splice the neutrals (the whites) together with a wirenut and fold them away. Observing the wiring diagram on the stacker switch, connect the black, full-time hot wire (coming from the last duplex receptacle where the wiring was reconfigured) to the "hot" or "line" terminal screw on the stacker. Next, connect the 3-wire black wire (going up to the fan/light) to either the top or bottom screw on the other side of the stacker; now connect the 3-wire red wire to either the top or bottom screw on the other side of the stacker. Now there are two switch legs going up to the ceiling fan/light location. At the fan/light, connect the fan black wire to the 3-wire black wire, and the light wire, blue, to the 3-wire red wire. And of course connect the fan white wire to the white wire in the 3-wire cable. Now the fan/light has two separate and connected switch legs, to operate the fan and light independent of each other, and a neutral wire. Of course, in this scenario the pull chains on the fan will be used to control the fan speed, and to control the light dimming levels, if so equipped.
BONUS: instead of the stacker switch, buy a 1-gang dual control fan/light switch. It is highly recommended that this dual control switch device be manufactured by the fan manufacturer, OR, better yet, a combination fan/light control switch device manufactured by Lutron - they build them right, with 6 or 7 fan speeds and light dimming levels -- a bit pricey, but worth every penny. Now the fan speed and the light dim level can be controlled from the wall controller, all fitting in the existing 1-gang box. What a package, nearly miraculous! And if there is access from above, probably no plaster cuts to repair, after running the new 3-wire from the existing switch box up to the new ceiling fan/light box. Another huge BONUS!! :)
For an inexperienced person this should take about eight hours, subject to attic access above to install the fan/light outlet box and fish the 3-wire down to the existing switch box. Don't forget to turn the power back on and enjoy the satisfaction of a job well done!!
Well, I hope I've done a good job explaining this and proof-reading it. I'll likely never be back to this particular post, but I do hope that someone will benefit from this oration. I am a nearly-retired Master Electrician with 45 plus years of experience in the residential electrical industry and hold a Class A Contractors License for nearly 30 years. I've done hundreds of very similar and successful installations. Cheers!