They usually won't accept children younger than 4 (école enfantine starts at 5 and is not mandatory)
Try the private Montessori schools.
I was very pleased with the bilingual French-English education they've had to offer.

It is a very good idea to put your child in a bilingual environment from the start, even more so if you intend to stay here.