The Vault describes both perks in shorthand with the following text:
Chance that
namewill finish off a target in VATS.
Where name is either Miss Fortune or Mysterious Stranger. However, the official perk text for them is slightly different. For Miss Fortune:
Just when your enemies think they have the upper hand, Miss Fortune appears to turn their world upside down. Appearing only in V.A.T.S., she has the ability to snatch defeat from the jaws of victory.
For Mysterious Stranger:
You've gained your own personal guardian angel... armed with a fully loaded .44 Magnum. With this perk, the Mysterious Stranger will appear occasionally in V.A.T.S. mode to lend a hand, with deadly efficiency.
Is there any functional difference other than gender, or is that it?