How to get recommendation letters for graduate admissions when my social anxiety makes it difficult for me to make connections?
I can see this is a difficult spot for you.  After all, to be good at your work doesn't necessarily require you to love interacting with people, but to get into the field you require letters of recommendation, which are best achieved by... interacting with people.

A few thoughts:


Are you more comfortable communicating over email?  If you can combine a good email correspondence with good course work, I think there's a path to overcoming this.  You can easily email your professors (using the less verbose style of your revised OP!) and ask about graduate school, research interests, and finally letters of recommendation.  
Have you taken classes with the same professors repeatedly?  This is one piece of advice I give to undergraduates a lot.  Each good semester with a professor helps reinforce the positive impression.  Assuming you still have one semester left before finishing, I would prioritize doing this again.  Speaking for myself, student's names I only see once are often quickly forgotten unless I've gotten to know them in person well, but student's names I see repeatedly start to stand out regardless, especially if they've done solid work.
Related to 2, have you taken only very large classes with the professors you want letters from?  If so, and if it's possible, you might try to get into a smaller section they're teaching even if it's of less (but not unrelated) interest to you academically.
You would be surprised how far showing up to office hours with good questions will get you, I think.  You said you've managed to overcome your anxiety enough to do this, and I don't think you should underestimate the benefit.  


In summary, find alternative ways to build relationships with the professors, through repeated interactions and electronic communication.  You don't have to be chumming it up regularly with your letter writers in person to get good letters of recommendation, though even the few visits to office hours you have managed will have likely helped.  Also make sure you read the posts others have linked in the comments regarding mental health issues and PhD admissions.

Good luck!