Network 2 players co-op lag issues

Hi there,

I'm currently adding a multiplayer co-op mode to my game and so far I've got some results but I'm experiencing lag issues and I was wondering if there is a better way to implement it.

A little bit of context

The game is a single screen puzzler, you move on a grid in 4 directions but it's not turn based, meaning time and latency are very important parts of the gameplay.
The logic is computed every frame just before rendering at 60fps and is 100% deterministic (no RNG)

Normal 1 player game loop

get inputs from keyboard or gamepad and compute game command (NONE, UP, DOWN, LEFT or RIGHT)
compute game logic
render frame

The approach I used to add multiplayer (2 players)

Player 1:

read received messages with command from Player 2
if there are more than 1 message, discard all but the latest game command from Player 2
compute self game command
send both its own game command and the one from Player 2 back to it
compute game logic
render frame

Player 2:

compute game command
send it to Player 1
read messages from Player 1 containing both game commands, there might be multiple messages for some reason
compute game logic for every message or don't if none
render frame

This way I'm sure both P1 and P2 have the exact same commands to compute the next frames and there are no desync. If P2 got multiple messages, it catches up to the latest state before rendering the frame.

Here's what it looks like (recording of player 1):

Issue
when there are multiple messages on P1 side, it really is not a problem for the gameplay and animation because it's not waiting at all and the game is doing one game logic pass per rendered frame, but when it happens on P2 side, the animation is choppy.

Thing is that I expect to have maybe 2 or 3 messages delayed and received at the same time but sometimes it a lot more like around 10 and it's really noticeable on P2 side.
I'm using ISteamNetworkingMessages interface for network communication and I send messages with k_nSteamNetworkingSend_ReliableNoNagle flags to try to minimize latency.

And all this happens while I'm using two computers connected locally to the same router in my office.

Any help or advice would be greatly appreciated

Thanks!