It needs to be easy to use for nontechies, reliable, conform to EU & French data storage regulations, and hopefully not be too expensive. The current onsite server contains only about 35 GB of data.
Do you have any specific recommendations or any advice on what to look for when searching for a cloud-based server service?
Not what you're looking for, as the software provided is more basic and won't meet your needs (although you could build something on top of this that would), but I host a couple of servers with GANDI and highly recommend them. Their prices are reasonable (if not the cheapest), they are an EU (French/Luxembourg) company -- with both US and EU datacenters; I host out of their US one -- and the quality of their service is by far the best I've found for small customers.
If you had a techy on staff, or were willing to hire a consultant, renting a virtual server on GANDI's EU data center and then deploying OwnCloud to it (or OwnCloud + a separate collaboration tool, like Confluence) sounds like pretty much exactly what you want.
35GB isn't much data, and paid yearly, you're probably looking at under 20 Euros a month.