wow! people can spend days responding to your post. lots of stuff there. I'm aware that I have no more wisdom or experience than you, I don't mean the following to sound like a sage giving advice to a novice... I'll show you my pictures, you'll see I have a lot to be humble about! (I stole that line from Yogi Bear.)
I spent about 25 years shooting with a 35mm rangefinder then went on a quick progression (5 yrs) through Mamiya RZ6x7, Canham 5x7, Sinar 8x10 and finally back to Sinar 5x7 as my ideal format. I also went through various film types, especially on the 35mm side, tri-x, tmax, apx 100, hp5, etc.
I've come to the following conclusions:
1. each format has a reason for being, use the right format for the picture. If tri-x medium format is too grainy, maybe it's a large format picture. Ever notice that, in a good people picture, grain is irrelevant?
Medium format is a compromise, you can use tri-x to mimic 35mm or tmax to mimic large format, but the results are never as good as using the right camera.
2. I've gravitated to the faster films in every format I shoot. be it for handholding in the small formats to wind issues in the larger formats.
3. Apparent sharpness is better than actual sharpness. A tgrain film in 35mm doesn't have the apparent sharpness of tri-x or apx in a larger format. apparent sharpness has 2 main components - edge effect and local contrast. (interesting that the 2 films you like (fp4 and tri-x) are strong in that department.) apparent sharpness should be judged by your finished print size. in my case, 5x7 tri-x makes a sharp grainless 11x14 which is my standard print size. If I printed larger, fp4 might be my answer.
4. one or two particular film/developer/paper combinations will look much better to you than anything else. experiment enough to find your favorites and then stick with them. once you make your pick, your technical angst will abate and you can spend your time on the image. My personal FDP combination is Tri-x 320 in pyrocat HD, printed on Bergger VCCB paper.
My life is now simple.
The one recommendation I would make is to try Pryocat with your favorite films. pmk has no advantage over it and your print times will be cut in half. It also works better than any other pryo developer in a rotary processor.