Experimenting with smaller boards
I did a computer search.
But 4x4 is too big for a brute-force search. The case 3x4 took a night to complete.
But here are the maximum nb of moves for smaller sizes:
1 2 3 4 5 6 7 8 9 10
1 | 0 1 3 6 10 15 21 28 36 45
2 | 1 4 9 14 21 30
3 | 3 9 16 24
4 | 6 14 24 ??
Note that in all these cases, the inverted board was among the worst cases. Sometime, as for 3x4, it is the only one.
Sometimes other starting positions are equally bad. For example, the following board for 2x5 is also a worst case with 21 moves:
4 8 7 6 0 -> 0 1 2 3 4
9 3 2 1 5 5 6 7 8 9
Upper bound for the 4x4 case
This does not answer the 4x4 case, but it gives a better upper bound.
As frododkywalker explained, the 1st row can be done in 18 moves. Taemyr noted that a first row at 18 moves + the 3x4 board at 24 moves gives an upper bound of $N \le 42$.
If the reversed board is the worst case then $N$ is even. This, with the trend in the table above, seems to indicate a value of $N=36$.
Lower bound for the 4x4 case
I could brute-force a simpler problem which is to reverse the columns of the 4x4 board and minimizing horizontal flips. I counted how many times you need to exchange any 2 numbers in 2 adjacent columns to arrive at a board where the outer left and right columns are exchanged and the inner left and right columns are exchanged. I arrived at 18 moves.
It is easy to solve that by hand, but it is not obvious it cannot be done in 17 moves.
If you use frodoskywalker's measure of disorder but only horizontally, you get a disorder of 32. And every horizontal move reduces it by no more than 2, this means a minimum of 16 moves. But that minimum cannot be realized. Because when you move out the first number from the left column, you need to put in a number from the right column to reduce the disorder. That means you need a number from the right column nearby. So you need to remove that number from the right column. But to do that while reducing the disorder, similarily, you need a number from the left column nearby. So the first move that affects a number from the outer columns cannot reduce the disorder, and therefore you need at least 17 moves.
The fact that you need 18 is a result of my computer search. Maybe some kind of parity is involved.
The implication for the original problem is that a solution that reverses the 4x4 board solves the simpler problem by columns and by rows. It reverses the columns left-to-right, which requires at least 18 horizontal moves. Likewise, it reversese the rows upside-down which requires 18 vertical moves.
That gives: $N \geq 18+18 = 36$.
Estimation for the 4x4 case
Note that sizes 3x3 and 3x4 are exactly 4 moves above frodoskywalker's minimum of 12 resp. 20 moves. It is my impression that this is a general formula. That would give $N = 32+4 = 36$.