Welcome, Faerie! I'm rather new to this all myself, but I have been doing yoga a bit longer than any of this other fun stuff like counting calories
When I started yoga, I started with yoga for larger (normal) women. I ordered online a book by Megan Garcia entitled Megayoga
and her DVD Yoga: Just My Size.
This was a great start and pretty soon I moved up a notch and ordered more advanced DVDs.
I have always felt weird in classes, gyms, and other places, too. Not so much my size, but it's just how I am. I dunno, maybe if their was a gym that blasted TOOL and had nothing but intelligent, tattooed, pierced, ex-junkies, who would want to talk politics and literature (not Oprah and Good Housekeeping) while pumping in a place that used energy saving bulbs and recycled plastic water bottles....I'd go there. So, my little at home exercise space as worked perfectly thus far.
Good luck on your journey! Joining this site is a great start!