So if two new blocks started from the same previous block, then the first to appear is taken as the "best" block, regardless of its content?
In this case, why do fee-less transactions are handled at all by the miners (each transaction requires at least the validation work)?
For now, the block reward is enough of an economic incentive for miners. In the future, as the reward goes down, it is expected that the transaction fees that some people choose to contribute will add up into a block to a respectable amount and take over as the primary incentive.
As it is, there is no advantage to mining an empty block, because the hashing is done against the 80 byte header only; and thus adding more transactions to the block is trivial. So miners add free transactions out of kindness. It's a form of charity that will become less common in the future. There will likely always be miners who are doing it for more reasons than simply the profit from mining itself, and these people are unlikely to reject free transactions. So in a successful Bitcoin future, traders who have a high value transaction are likely to be contributing a transaction fee in order to have their transaction processed in a timely manner; whereas small transactions, transactions involving external trust (i.e. from friend to friend), and basic donations are likely to have to wait to a lull in the network. Furthermore, free transactions are prioritized based on how long the (youngest?) input have been in the blockchain, oldest being of the highest priority so that spamming of the network can't significantly delay an honest transaction lacking a fee.