To be clear, the way (most) exchanges solve this problem now is by what's called "queue" priority. The longer an order has been resting at a level the higher it's priority is.

This means that those who can respond faster can get into a price level sooner. Breaking this out to minute bounds doesn't mitigate their advantage in any way shape or form.

It is hard to know what the results of a change like this would be. I suspect it would make the markets much less stable as there would be less information to make accurate prices, causing huge variances on minute long ticks.

This is not a problem that today's electronic markets avoid. They have to answer your question too!

Either first-come-first-serve, but that would give you some form of high-frequency again, or you just pro-rate them or fulfil them randomly.