Hello Sam, congratulations on the job and the exciting move to Paris!
To echo a lot of what people are saying, not sure there’s currently a French bank that fully meets your requirements. I think the big battle in French retail banking is the challenge to fee based banking. Hello, Orange (sorry Andre) and Nikel are the main contenders in this race.
As has been previously mentioned you could encounter IBAN issues with a non FR domiciled bank, so it might be useful opening a French domiciled account if you’re planning on establishing yourself there. Where your salary is originates is also worth a consideration, as your employer may not pay into a French domiciled bank.
A couple of my friends use Hello, which is essentially BNP Paribas and they have had no drama, and just pretty happy they don’t have to pay a monthly fee for essential transactional banking (!)
Personally, I use a combination Banque Courtois (cobwebs) and HSBC, formally a BNP customer, but I closed that to switch to HSBC, as I hold an account with them in the UK. It made opening (marginally simpler), plus their Global View product made it easy and convenient to transfer without fees, though offered FX isn’t competitive.