You may not have the time to do this, but I credit a lot of what social grace I have to working a retail job during and after college. I wasn't much of a partier in my teenage years either, but I can talk to a pretty broad range of people, because for years my boss was whoever walked in the front door. Maybe you could spend some time in a similar setting, even just an hour or two of volunteering at some public-facing event. Registration booth for a marathon, anything really. In that kind of scenario, it's like training wheels for empathy: you already know, roughly, what the other party wants (to register for the marathon), so it'll take that burden off and give you a chance to study the minor details of body language, small talk, all that sort of fun schmoozy stuff. And you can't really fail, as long as the runner gets her number and cheap t-shirt.
In contrast, in a social setting, those sorts of hard-to-quantify details are basically all that's going on, which I think makes it harder to focus. After all why does anyone go to a party? Those motivations are really vague, and maybe the people at the party don't even know what they are. Trying to understand how that works is building on quicksand.
To try to answer some specifics: Bill Gates has a weird life, unlike most of us. I've worked with other people who started successful companies straight out of school, and they were unapproachable too, perhaps because they'd never had a boss. They weren't good at math either. As far as enunciation, volume, thinking of the next sentence: I think the suggestions to try Toastmasters could be a great answer there.
So I guess my suggestion is: empathy is what makes people approachable, so find an environment like sales or service, where empathy is tightly tied to the goal, as a place to practice it. The books like Dale Carnegie definitely help, but practice makes perfect.
Good luck!