Interesting board sizes
7x7, 9x9 (+2), 13x13 (+4), 19x19 (+6), 27x27 (+8), 37x37 (+10), ...
This sequence can be captured by the formula n^2+n+7.
Bildstein: Let me be the first to disagree: Although you found a formula that correctly gives 9, 13 and 19, I think if anyone ever plays on a 27x27 or 37x37 board, they will find them not particularly interesting.
I think the reason for the 9,13,19 progression is this: 19x19 is an appropriate size, as described elsewhere on this site, 9x9 is approximately half the size of the 19x19, and 13x13 is approximately helf way between the two (as an intermediate step between playing on 9x9 and playing on a full sized board, perhaps).
Coconuts: Old games in Japan were played on a 17x17 board, and they experimented with 21x21 boards as well. I think any board size can be interesting (even 2x2 if you're looking for the right thing), even or odd, small or large. Go is so adaptable that it almost doesn't matter (or you can look at some of SL's investigation into lineless go).
Rubyflame: Count the number of intersections. For 9x9, you have 81 intersections. For 13x13, you have 169 intersections (compare to 2*81 = 162). For 19x19, you have 361 intersections (compare to 2*169 = 338).
In each case, it's the closest odd-sized board you can get to twice the previous board size. This also suggests that a 13x13 game takes about twice as long as a 9x9 game, and a 19x19 game takes about twice as long as that.
By this formula, the next sizes are 27x27 and 39x39.
Jens?: I think 17x17 is the 'correct' sized board and 19x19 was just an interesting variation that stuck around (playing on the edges of a 17x17 board to make a 19x19 board). I believe the progression is 3x3, 5x5, 9x9, 17x17, and the next would be 33x33, and then 65x65. If you take four squares and tile them together you get a 3x3 board (where the edges become the lines), and four 3x3 boards tiled together make a 5x5 board, and four 5x5 boards together make a 9x9 board, and four 9x9 boards make a 17x17 board. The pattern is that each board size is made by tiling together four of the next smaller sized boards (where the lines are nothing more than edges of tiles). And the equation for the width is n(k) = k ^ 2 + 1 where k is a natural number. Of course we can play on any size board we want, but if this wasn't the pattern,... then it should have been. ;-)
bin?:One problem with all the ideas here are that they assume a interesting board would need to be a square one, just because the ones we play are square sized ones. So people are are making math using only the size of one axis of the board, instead of using the number of squares the board has and also the board ratio( because a 1x81 board is very different from a 9x9 board but have the same amount of squares) to do it. Also people are assuming that if 9x9 board is interesting and then 13x13 is also interesting, there are no boards between 9x9 and 13x13, talking about row * collumn, row size, collumn size or collumn +row, that are interesting.