Renting can be a real headache for newly arrived foreigners. Part of it is that there is no centralized "credit rating service" like you have in North America, so the agencies and the landlords tend to use the "classic" criteria, which includes three months of pay slips.
You may want to take a look at the information available about renting on the PAP (Particuliers à particuliers) website.
https://www.pap.fr (They also have a very informative section on buying property there.) PAP is the big resource for buyers, sellers and renters and landlords looking to "avoid the middle man" of agents and agencies. Since you already have good French, this could be a good alternative for you.
The rental market in France can be very tight - and most landlords with decent properties have multiple dossiers they can choose from (so they tend to jump at the "easiest" potential renter). It's also the case that many rental properties that are turning over won't be available to be seen more than about a month before the turnover date - and in some areas a "nice" place will be snapped up within the first few days on the market.
OTOH, if you buy right away, you may find the "gotchas" about the area in which you decide to buy - and homes do not turn over as quickly or easily here as they do in North America. It can take a year or more of renting to get to know the various districts and areas in the town or towns you think you are interested in.