The part you are missing about the encounter between Paul & Fenring is prescience. The prescient cannot see other prescient people in their future sight.
Paul had the edge on Fayd because of his future sight. Fenring was close enough to a Kwisatz Haderach to be invisible to Paul's prescience so the outcome of a fight would be a complete unknown for both people.
There are two legs of the Kwisatz Haderach breeding program which converge in the birth of Paul. Given that Fenring was part of the same breeding program, it's almost certain that they are related. Given their age it is likely a close relation.