05AB1E, 12 bytes

ÅΔεN²+£}JIÅ?

Inputs in the order \$listOfNames, gender, trigram\$, where \$listOfNames\$ is a list of pairs of uppercase strings (e.g. [["JOHN","DOE"],["JDANE","ORWELL"]]); \$gender\$ is either \$1\$ for male or \$2\$ for female; and \$trigram\$ is uppercase as well (could also all be lowercase, as long as casing is consistent for both \$listOfNames\$ and \$trigram\$).

Try it online or verify all test cases.

Explanation:

ÅΔ      # Find the first (0-based) index of the first (implicit) input-list that's
        # truthy for:
  ε     #  Map over the current pair of [firstName,lastName]:
   N    #   Push the current map-index (0 for firstName, 1 for lastName)
    ²+  #   Add the second gender-integer input
        #   ([1,2] for males; [2,3] for females])
      £ #   Leave that many leading characters from the string
  }J    #  After the inner map: join these prefix-strings together
    I   #  Push the third input-triagram string
     Å? #  Check that the joined prefixes-string starts with this triagram
        # (after which the found index is output implicitly as result)

Note: even though we have [2,3] instead of [2,1] for females for the [firstName,lastName] respectively, because we check if the prefixes-string starts with the tiagram-string instead of being equal to it, it still works as intended.

Dyalog APL, 24 chars

Takes the trigram and marker (1=female) on the left and list of tuples of first/last name on the right.

"You may take input strings capitalized how you see fit" - I took that to mean I could lowercase everything on input.

{⊃(⍵{∊⍺↑⍨¨⌽⍣⍵⍳2}¨⊃⌽⍺)⍳⍺}­⁡​‎⁠‎⁡⁠⁣‏⁠‎⁡⁠⁢⁢⁡‏⁠‎⁡⁠⁢⁢⁢‏⁠‎⁡⁠⁢⁢⁣‏‏​⁡⁠⁡‌⁢​‎⁠⁠⁠⁠‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏⁠‎⁡⁠⁢⁡⁤‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌­
  (                 )⍳⍺   # ‎⁡Index of the trigram(*) in
                 ⊃⌽⍺      # ‎⁢Take the last element of the left arg (the marker)
   ⍵{          }¨         # ‎⁣And run it with each of the tuples of names
             ⍳2           # ‎⁤1 2
          ⌽⍣⍵             # ‎⁢⁡Reversed 0 or 1 times, depending on the marker
      ⍺↑⍨¨                # ‎⁢⁢And take that many characters from the input tuple.  So this either takes 2 chars from the first part and 1 from the second, or 1 char from the first part and 2 from the second
     ∊                    # ‎⁢⁣Flatten that string
 ⊃                        # ‎⁢⁤Get the first element of the answer.
                          # ‎⁢⁤(*) Index was run on both elements of the left arg but we only care about the first one, the trigram
💎

Created with the help of Luminespire.

Python 3.8 (pre-release), 62 bytes

lambda t,g,a:[t==b[0][0]+b[g][g^1]+b[1][g]for b in a].index(1)

Try it online!

Port of Arnauld's JS answer.

Haskell, 52 bytes

h t g n=[x|x@[f,l]<-n,[f!!0,x!!g!!(1-g),l!!g]==t]!!0

Try it online!

PowerShell, 73 69 bytes

Param($t,$g,$s)$s-match("^$($t[0]).*? $($t[2])"|% I*t(2,6)[$g] $t[1])

Try it online!

-4 bytes because of a d'oh moment where I left 4 unnecessary brackets in the regex from an earlier attempt with -replace.

Expects gender as 0 for F, 1 for M, and the names as an array of "FirstName LastName".

Constructs a regex from the trigram based on the gender and matches against the names:

F: ^$t[0]$t[1].*? $t[2]
M: ^$t[0].*? $t[1]$t[2]

Ungolfed:

Param($t,$g,$s)  # Trigram, Gender, Strings
$s -match (      # -match against an array will return all elements that match
    "^$($t[0]).*? $($t[2])" | ForEach-Object -MemberName Insert (2,6)[$g] $t[1]
                 # Constructs a partial regex for a trigram XYZ as "^X.*? Z", then inserts Y depending on gender either after the X (at index 2), or before the Z (at index 6)
)

PowerShell, 70 bytes

Param($t,$g,$s)"$($s|?{$t-eq"$($_[0][0])$($_[$g][!$g])$($_[1][$g])"})"

Try it online!

Expects gender as 0 for F, 1 for M, and the names as an array of ["FirstName", "LastName"].

Constructs the trigram using the gender to index where required (that is, where the indexes differ between F and M):

F: $s[0][0] $s[0][1] $s[1][0]
M: $s[0][0] $s[1][0] $s[1][1]

Ungolfed:

Param($t,$g,$s)                                        # Trigram, Gender, Strings
"$(                                                    # Open a string, and start a subexpression
    $s | Where-Object {                                # Pipe the array of names to Where-Object; each iteration will process a two-element array with FirstName, LastName in $_
        $t -eq "$($_[0][0])$($_[$g][!$g])$($_[1][$g])" # Construct the trigram from first and last name, and compare against the trigram parameter
    }                                                  # Where-Object will return the first and last name where the trigrams matched
)"                                                     # Enclosing the two strings inside a string will automatically join them with a space, returning the full name as single string

JavaScript (ES6), 48 bytes

Expects (trigram, gender, array) where gender is 0 for female / 1 for male and the names in array are [first_name, last_name] pairs in upper case.

Returns one of the pairs.

(t,g,a)=>a.find(b=>b[0][0]+b[g][g^1]+b[1][g]==t)

Try it online!

Commented

(               // anonymous function taking:
  t,            //   t = trigram
  g,            //   g = gender (0 = female, 1 = male)
  a             //   a[] = list of names
) =>            //
a.find(b =>     // for each name b[] in a[]:
  b[0][0] +     //   1st letter of first name
  b[g][g ^ 1] + //   either the 1st letter of last name (if male)
                //   or the 2nd letter of first name (if female)
  b[1][g]       //   either the 1st (if female)
                //   or 2nd letter (if male) of last name
  == t          //   check if that's equal to t
)               // end of find()

APL+WIN, 57 bytes

All characters lower case. Index origin = 1. Prompts for gender: male = 1 female = 2, then trigram, then nested vector of second names and finally nested vector of first names.

g←⎕⋄k←⊂g↑t←⎕⋄l←⊂g↓t⋄(3=(+/¨k=¨g↑¨⎕)++/¨l=¨(3-g)↑¨s)/⍳⍴s←⎕

Try it online! Thanks to Dyalog Classic

Google Sheets, 43 bytes

=filter(B:C,A1=left(B:B,2/A2)&left(C:C,A2))

Takes gender as 1 for female and 2 for male. Outputs [firstName, lastName] in a spilled array. This works because string comparison is case-insensitive in many spreadsheet contexts.

Retina 0.8.2, 46 bytes

i!`(?<=(.+)((?(4).).)¶(F|(M))(.|¶)*¶)\1.* \2.*

Try it online! Takes input on separate lines but link is to test suite that takes a list of comma-separated inputs for convenience. Explanation:

i!`

Search case-insensitively and output matches.

(?<=...¶)

Match after a newline.

(?<=...(.|¶)*...)

Search back to the beginning of the input.

(?<=...¶(F|(M))...)

Capture whether the employee is male.

(?<=(.+)((?(4).).)...)

Capture the last two letters as the second prefix if so, otherwise just one letter, and the remaining letters as the first prefix.

\1.* \2.*

Match each name against the appropriate prefix.

Charcoal, 16 bytes

Φζ⁼θ↥⭆⪪ι …λ∨⁺ημ²

Try it online! Link is to verbose version of code. Takes the gender as 0 for female or 1 for male and outputs all matching names. Explanation:

 ζ                  Third input
Φ                   Filtered where
       ι            Current name
      ⪪             Split into spaces
     ⭆              Map over parts and join
          λ         Current part
         …          Truncated to length
             η      Second input
            ⁺       Plus
              μ     Inner index
           ∨        Logical Or
               ²    Literal integer `2`
    ↥               Uppercased
  ⁼                 Equals
   θ                First input
                    Implicitly print

Jelly, 12 bytes

ḣ"Ḋ^Ƭ3Ɗ}FeʋƇ

A dyadic Link that accepts the choices on the left, as pairs of [first_name, last_name] in uppercase, and a pair on the right containing [trigram, gender], where gender is 1 for male and 2 for female, and yields a list of the matching choice(s).

Try it online!

How?

ḣ"Ḋ^Ƭ3Ɗ}FeʋƇ - Link: Names; [trigram, gender]
           Ƈ - keep the {Names} for which:
          ʋ  -   last four links a dyad - f(Name, [trigram, gender]):
      Ɗ}     -     last three links as a monad - f([trigram, gender]):
  Ḋ          -       dequeue {[trigram, gender]} -> [gender]
    Ƭ        -       collect up while distinct under:
   ^         -         XOR with...
     3       -       three
                     -> Instructions = [[gender], [gender^3]]
                                     = [[1], [2]] (male)
                                    or [[2], [1]] (female)
 "           -     {Name} zip {Instructions} with:
ḣ            -       head {NamePart} to 1-index {Instruction}
        F    -     flatten
         e   -     exists in {[trigram, gender]}?