Miners are the ones that ultimately choose the order of the transactions.
The transactions in the block are chosen by the miner who mines the block. These transactions are usually the transactions that will pay the miner the most (the highest fee), but this is not always the case. The miner may, for some reason, want to choose a transaction that is not the most profitable.
Proof-of-authority works the same way. The miner chooses the transactions included in the block.
How can these nodes fairly decide on when to execute transactions?
The choosing of transactions is questionably fair. Miners can and do choose and order transactions in whichever manner they desire. This is considered fair, as they did the work to be in the position to be able to choose these. This may be considered unfair as well, but it is a tradeoff that was made by the Ethereum community (the alternative would have been to lower the block gas limit, which would allow miners to include less transactions. This would, in turn, decrease the max TPS of the network).