What is a good higher-voltage alternative to the TI TPS2113A power mux?
The classic solution is using a wired-OR connection, but to replace D1 and D2 with two ideal diodes chips. Unfortunately, your battery voltage is higher than the line power, the battery will always be on, and this solution is unusable.



Since you want to avoid SMD parts, You have to find an alternative power mux module with a breakout board, but there aren't many, it seems.

Or you can try designing a discrete solution similar to an ideal diode/power mux. The idea is to use a LDO to power an ultra low-power comparator, which in turns switching a logic-level MOSFET before its own power runs out. The reference voltage can be derived from the LDO simultaneously. Both inputs of the comparator are scaled down with a resistive divider. Here's an example, it needs some modifications before it's usable.



However, the most sensible solution to me, is still using a SOIC power mux chip and solder it on a breakout board.

Another solution is simply to keep using your power mux, and add a buck-boost converter to your battery to maintain a constant voltage of 5 V. Buck-boost is extremely common in the commercial market, you can just search for buck-boost converter controller chips at an electronics supplier's website, such as Mouser and Digikey. If you need a breakout board, simply search "buck-boost breakout board". Just for starter, Sparkfun has a TI TPS63070-based breakout board. It comes with an efficiency penalty, but perhaps it's already adequate - A SMPS is 80%+ efficient under full load, and it enters a powersave mode when there's no load, only consumes power at a level of 100 uA, and it can always be disabled to save more power if line-power is available.