Plain and simple - What battery works best with this?
Depends in my experience from the definition of “this” :-).
Just the feather, which has a 2pin JST-PH (2mm)? Or the GPS Enclosure, which comes with a 18650 battery holder? Rechargeable or not? Intended time to operate from battery? Temperature range?
For common usage, a rechargeable LiPo is a good match.
For 2pin JST-PH I frequently use one of those LiPo JST-PHR or, if larger capacity or 18650 is required LiIon JST-PHR/18650. The shop is in Germany, so for outside Europe it’s more intended as examples.
In some cases, when I expect to run over a couple of years and not only 1-2 years, I also use NiMH LSD cells (mainly Eneloop, 3xAA 2000 mAh). The intention is then to send once a day with CoAP/DTLS 1.2 CID, otherwise the device will not reach that number of years.
For solar powered devices I use super CAP, LiHybrid 400F.
All those options operates in similar temperature ranges, with the main downside, that you should not charge below 0°C, which maybe an issue for solar powered outside devices in winter.
Hope that helps to see “plain and simple” requires a common use-case. if the use-case differs, the common choice may be wrong.