How about:

A race where everybody brought out their best in order to win.

as for the sentence I think: "a race that everyone was eager to win and in which everyone gave their all/put their best foot forward"

Who is criticising you for using "themselves" in conjunction with "everyone"? Grammatically the criticism is correct but in common parlance we tend to use the third person plural with pronouns referring to "everyone/everybody" to avoid the thorny issue of him/her and s/he. Having said that, it can be difficult deciding what to do as the overall context needs to be taken into account as well.

I'm dealing with a speech at a business conference - so it should have style and be emotional but it's a speech held by a native speaker addressing several nations...so it's not a written thing...it's supposed to sound natural and fluent:-)

I think you'd be fine using "their" in this case. I'd be very, very surprised if any native English speaker were to complain ;-)

Haha, those who complain usually are German clients who have spent 3 months or a year in the US or Britain:-P