In addition to many successes with Rodinal and large format in general, I often have the problem you describe with Rodinal, with smaller formats in particular. Any individual section of the print looks very good, but when I look at the whole print I can't quite define the problem, but put it down to "compressed mid-tones.
Recently I did a shoot with FP4+ in 35mm with a wide light latitude that printed well. I exposed at ei 50 with an averaging meter, and developed in Rodinal 1:50 agitation continuous for 30 seconds, then two agitations at the to of every minute up to 12 minutes, with a coast to 14-1/2so, a little longer coast.
For flatter scenes where I want to add contrast, I have been using dilutions of 1:25 with greater success.
As for FP4+ in D-76 1:3, this looks great. I use 18 minutes at 68° for small format, and 20 minutes for large format. Make sure you use enough stock solution so that your developer doesn't exhaust. The shot of the barrels in my gallery was developed this way. (there was a url link here which no longer exists)