Why aren't public-private keys sufficient to build a block chain? Why do we need proof of work/stake? Taking the simple case of Bitcoin here:
If all nodes can validate published transactions by checking the signature (created using the private key of the sender) of the transaction against the public key of the sender, why isn't that sufficient to validate a block?
I understand that we also solve the puzzle of finding a nonce that when combined with a block's contents, gives us a hash that has N number of leading zeroes. Why do we need this at all? Isn't it enough to check the validity of each transaction in the block?
As for double spending, if a miner decides erroneously to include both transactions, nodes can see there isn't enough balance and reject such blocks. As for which transaction of the two to take, the code could have a way to order transactions and if an attacker decides to do the opposite intentionally and decides to spam the network (since there's no proof of work cost) but how does the attacker benefit from that?
the code could have a way to order transactions and if an attacker decides to do the opposite intentionally and decides to spam the network

This is the crux of the issue: how do you achieve this? It isn't a trivial problem to solve in a decentralized network. The more generalized version of this non-trivial problem is called the Byzantine General's Problem, it describes the ability of participants to come to an agreement in an untrusted network. The invention of bitcoin provides an economically-incentivized game-theoretic framework that could be considered a probabilist solution to this problem.  As @PieterWuille mentioned in the comments, there is no absolute guarantee of eventual consistency: there is only a (continually increasing, thus far) economic incentive for participants to consider.
The solution that proof of work provides is to rate-limit spamming via the requirement for expenditure of a scarce resource: energy. It is hard to create a new block (it takes some amount of energy, on average), but it is easy to verify if a block is valid. And remember that the method for choosing the next valid block must be perfectly consistent across all nodes in the network, or else you risk a network split/fork, which is very undesirable.

but how does the attacker benefit from that?

There are many ways an attacker could benefit. As a simple example: the attacker takes a 'short' financial position, betting against the price of bitcoin. They then attack the network, assumedly causing the network's value to drop, and thus they would profit from their short position.