Definitely a French school, state or 'private' Catholic (which are not like UK independent schools). I've lived in France and worked in French schools (not when I had school age dc, so no experience as a parent). The system is different from the UK, less flexibility and more traditional, but still a good system. If you're moving to a big city, there will be schools who are used to taking non-French speaking pupils.
I would still hire a tutor to help get their French up to scratch as quickly as possible. Some of the children I know who moved around that age were fluent with speaking pretty quickly (well within a year), but struggled with grammar for a lot longer. The vocab will come pretty quickly, but the French school system is not forgiving of poor grammar and syntax.
It's less common nowadays, because of the financial implications, but it's possible for children to repeat a school year in France, they don't automatically move up with their age group, it depends on their results. They have to 'pass' the year to move up. When I taught in a lycée, some of the final year pupils were in their early 20s, having re-taken a few years along the way.
I would keep the option of transfering to an international school to yourself. Don't let dc know that it's on the table, but have it in the back of your mind if things really don't work out. However, I would only transfer as a last resort. The beneifts of being bilingual and really integrating into the French community and culture can't be overestimated, you'd be setting dc up for life. Ok, it's not as ideal as moving younger, but it's still a great opportunity.