There are no "not-legitimate" transactions. Just ones that end up in the chain and ones that don't.
Yes, there is. The tx which was broadcasted first is legitimate and any other transaction that is broadcasted later is non-legitimate.
And the network knows which one was broadcast first through what mechanism exactly?
In our universe, there are limits to the speed that information can travel. Which means that "first" is not a globally meaningful concept, only a local one. The blockchain is an attempt to achieve a global ordering using only local information.
If a user is concerned that they might be dealing with someone who would try to back out of paying then they should use Bitcoin's built in solution, wait for confirmations.
There are use cases where you don't want to wait for confirmations.
Bummer.