We live in the Midwest in a large home that was built 20 years ago. At the time, we installed two 75-gallon gas water heaters, and the plumber did this in series, not parallel
That is the correct way to do it. This will become more clear once you understand how water heaters work, in particular, how hot water stays separated.
https://www.youtube.com/watch?v=Bm7L-2J52GU
If the system is not performing to spec, you should maybe contemplate that it might be broken. For instance, if sacrificial anodes have not been maintained, it's possible a dip tube sacrificed instead. Or, one of the heaters may simply be inoperative.
Sometimes, when there are 6-8 of us in the house, we know that the hot water will be out after the first or second shower. And often we don't have enough hot water when just 2 of us shower in sequence.
That shouldn't be possible, unless you have a very unusual sense of what a shower is.
You should be able to get honest 125 gallons of stable hot water out of this setup. Let the whole system reach 'quiescent' (heaters achieve temperature) and then run a test. Go to a spigot, get a bucket and stopwatch and figure how many seconds to flow 1 gallon. Multiply by 125 and see if you can get that many seconds of reliable hot out of it.
Try slapping on California low-flow showerheads and rigid 10-minute timers on showers, and see if that helps. A 10-minute California shower should only use 15 gallons of hot water, tops.
We also have a system of pipes for hot water recirculating to each of our fixtures.
That's not helping. Aside from being wasteful, some of those circulate water onto the cold line! So now, instead of being consistently cold, the cold water line has variable temperatures. So you adjust the hot/cold to the temp you want, and it keeps changing... you think "the hot temperature is not stable" actually the COLD temperature is not stable! That "recirculate back onto the cold line" only works if you have self-adjusting thermostatic mixing valves i.e. the fancy joystick faucets.
Also most of those recirculators are cheap, and may well have failed, e.g. be circulating when they should not, or be leaking cold water back into the hot pipe at inopportune moments.
(1) just replacing the hot water heaters;
Sure, that will accomplish "replace anodes and check dip tubes", kind of an expensive way to do it though.
(2) replacing them and repiping them to be in parallel instead of in series;
"try everything"? No, that'd be worse for sure. Unless you split the house's piping so 1 tank serves half the house and the other tank serves the other half.
or (3) replacing them with one tankless gas
You guys seem really into simultaneous showers, so you might want to get California showerheads if you do that. I've seen tankless gas go not so well. My rule of thumb is 34,000 BTU* per GPM.
* This equipment is rated in "BTUs" per trade industry habits... but actually this means BTUs per hour. If you really want to get into brass tacks (and it might be worth doing so), a "BTU" is the energy needed to heat 1 pound of water 1 degree F. 8.3 pounds of water to a gallon, 60 minutes in an hour. So you can convert GPM into pounds per hour. Multiply by degrees rise in temp desired and you arrive at BTU/hr, commonly called "BTU" :)