OVH (english website [1]) is the best French hosting company and one of the best French domain name registar (with Gandi [2]), and are starting to make themselves a name outside of France. Hubic is the "cloud" offer from OVH. They both have quite a reputation of being reliable and very responsive, and have very fair prices (they are like the hosting counterparts of Free [3], a French ISP that drove subscription fees…
Have you ever dealt with their support? - I for myself am quite happy with my service (Dedicated server) so far (because I rarely had to deal with the support) but I've heard a few horror stories where some of their biggest UK customers basically got kicked out even though they stayed within the TOS and the terms they signed the contract for, or the thing about their DDoS protection kicking in, rebooting your server even though they are legit requests.
You can't beat their prices though.