I always figured the best bet was to find a bisexual person, because there's more of an off-chance that the person won't be bothered by the parts, because they already like you for you, and the gender parts aren't as important.
Also, relationships aren't completely about sex right? If the first thing they want to do is jump in bed, hon, you need to find better men! If you look for one that is looking for a committed relationship, you might be in luck. Anyone who's been around the block knows that sex is only part of a good relationship. It's about the person, compromise and so on, though I might be wrong.