You can find Tri-Faces on the Island Closest to Heaven, and in the Deep Sea Research Centre (DSRC).

In the DSRC they're in the "First Battle Arena", or the first screen past where you take the lift down, and expend you're remaining Reserve Steam Pressure (RSP). There's a save point there, and you begin your decent down all the stairs to the bottom. Anyways, every battle here is with a Tri-Face.