You can't have sex with most NPCs, regardless of gender.
There is a bigger chance if you have Lady Killer/Black Widow and/or Confirmed Bachelor/Cherez Le Femme as you might trigger conversation options that trigger sex. Or you can always go to Gomorra and hire one of the lovely hookers in the courtyard, or talk to Old Benny in the Atomic Wrangler after the Wang Dang Atomic Tango quest. Or, if your mentally troubled, you could have sex with Fisto or Beatrice after the same auest.
Everytime you talk to Fisto about sex but don't do it you get 10 caps. He's the fist that keeps on fisting.