Obviously for $n=2$ the maximum is $1$. It's not much harder to see that for $n=3$ the maximum is $3$ (just go through the cases). I ran a script to pick books at random repeatedly so I don't know for certain that I found the maximum, but the highest number I got was $7$ for $n=4$ and $15$ for $n=5$. But a formula (or recursion) would be very nice and a proof even nicer. (Those numbers look like $2^{n-1}-1$ so far but I don't think that that continues.)

I've seen this problem before, I but can't remember the details. One thing which does stand out is that the extrema settle. If you consider e.g. ordering $1,2,5,3,4,6$, the $1,2,\ldots$ and $\ldots,6$ are now fixed.