My experience is that French is flat (rather monotonous rhythm and stress is much less important than in English). This makes it somewhat easy to follow for foreigners after some training compared to e.g. Spanish which is typically all over the place and very fast (though not more difficult once you get the hang of it).

On the other hand French speaker can get confused by strange intonation or stresses. Also there are several sounds that do not exist in English (e.g. /eu/, /u/, and the nasals /an/, /on/, /in/, the /ill/ can be problematic as well). Approximations of these sounds are distracting and can be genuinely confusing. And contrary to some English accents you can’t count on properly stressed syllables to help carry the meaning.

During my time in New York I had the opposite problem. As a native French speaker with some English education (having lived in London), apparently people understood me without difficulty. On the other hand, it took me a while to get the meaning of what other people were saying without asking them to repeat. After months it was still difficult to understand announcements in the subway.