As both an introvert and someone with social anxiety, I feel what you're saying.
I have over five decades of coping strategies, and a lot of directed work like taking public speaking classes to improve, and I still can't stand things like work gatherings at a bar. Blech.
First things first, your idea of looking for your peeps is a good one. A FLGS will be full of members of the gaming tribe But when talking to them takes them away from things they are already involved in, not interrupting is the right call. As others have mentioned, show up early. That also allows you to get to know a person at a time as they come in which is much easier and less imposing than a group that's already chatting.
If your FLGS is just providing space and anyone can set up games, consider signing up and bringing one you know. This means people will be coming to you and introducing themselves. A variant on this is bringing a favorite obscure game that's straightforward to learn and a sign "Learn to play XX".
Helping people falls into a whole different mental/emotional category for me than social introductions and small talk.
Tap the people you now know to introduce you to others. Going up to someone cold is hard. Having someone who knows them go "Hey, have you met
@Kaodi yet?" is much easier. (And the flip side of that is remember to do that for others, a lot of us gamers will appreciate the help.)
Wear a shirt with something vaguely related you like on it, giving others another opening to approach you. "Hey, I really liked Project Hail Mary too!".
Remember it's not random small talk, you've got the games, the FLGS, and all that related stuff to talk about. "Have you been part of the game night for long?", "What's that guy's GMing style", etc.
I have trouble remembering names, and I flip that around to leverage it. When I meet someone new I mention it, and repeat their names back to them. Makes them feel special, worth remembering. And if I want to talk to someone later but don't have an icebreaker I just use that -- "You're Eddie, right?".
Best of luck!