I'm a guy without a regular dance partner too. Typically, guys in our situation work with a female instructor. I've done an occasional lesson with a male instructor to get some tips on leading and men's styling, but you need to dance with a female to learn how to dance with women. Women taking lessons on their own do so with a male instructor, so why wouldn't we take lessons from a woman?
You should tryout a variety of instructors until you find a really good female instructor who can teach you how to lead. She may do some back-leading initially, but this is just to get you started. The female instructors I've had all really enjoyed leading, and would often dance with other women at the practice parties.
Good luck.