13x13

n has to be odd because the number of coins is odd. 15x15 needs at least 112. So 13x13 is the largest. First place one coin at each of the four corners and alternate between rows and columns. We have 7x7+6x6=85 coins. Then place two coins at 13 places where there are no coins.