I'm your Huckleberry
I'm 5' 11.5" tall, with a 32" inseam. I ride an M 18.5" NRS(race only bike) as well as an L 20.5"(trail/race bike) daily. Both fit, but you'll prob like the 18.5 better from your description. I run a 110mm stem on the L frame, and a 120mm on the M. Shorter stem on the M frame and I start worrying about hitting my knees on the shifter/bars while steering and climbing out of the saddle. With a shorter fork like an 80mm Sid or equal, combined with the 120mm stem, the bike feels endo prone-ish sorta over logcrossings and such. With a 100mm fork, its perfect. In comparison, the L feels long and a touch slow in the tight stuff. Not quit as twitchy feeling maybe tho. Somewhat more stable in the rough(due to the 1" longer wheelbase). Doesn't climb quite as well since the frames longer from by 1" from the BB to the steertube. One must lean farther forward to transfer more weight up front on the short steeps. No biggie, but since I swap back and forth, I can notice it. Noticeable less standover as well, which will be less then your 19.5" Trek. I run max post(meaning its even with the bottom of the shim with a 350mm Alien carbon)with the M frame.
For reference, my 19" Schwinn Moab HT fits me perfect..so I suspect I need a 19" NRS, but alas....