After trying a few different options I have ended up on the (seemingly very uncool) Pimsleur program (available for cash lump sum or monthly. I am paying monthly). For me, one of the biggest challenges in French is how a lot of words get blended together and are spoken very fast. It's easy to hear what seem like new words, but they're actually things I know, but spoken as native speakers do. This listening concept is extremely important for me with French in particular. To contrast, I speak Swahili too and learned it differently, where I wouldn't say there's as much of a demand for emphasis on listening to native speakers.
Some other alternatives I tried first include:
Chatterbug: Nice combination of tools/methods, but expensive and I'd need to pay a much higher price to get the kind of listening I need. A side note on these guys that's relevant for this site: they do a lot of ruby/rails stuff and have a nice graphql gem called cacheql.
French Uncovered: Interesting idea and fun method of learning, but the "book" material wasn't as long as I'd have liked and I would have liked to do a lot more listening. The self-study written materials are decent, but felt slow and like a forced way of trying to cram information into my head, where I personally do better getting that stuff naturally.
Language Transfer: Great free option, but doesn't have native French speakers and the French course doesn't good too far.
I've also done the apps like Duolingo, but the listening and speaking isn't what they do best. I basically get great at Duolingo, but not at being able to use the language.