I think it's pretty amazing how good you get in this game once you play it a little more. At first it's simply impossible, but you start to recognize the patterns pretty quickly and you can usually beat the 3x3 ones in less than 10 moves.
You should never have to use more than 9 moves for 3x3. Hitting the same square twice has no net effect, even if the two moves on the same square are separated by other moves.
You can actually knock that down to 8 moves (maybe less?) as the max required for a solution. You never have to press the middle square, since it flips every square, inverting the board. Inversion doesn't bring you closer to the checkered pattern of the chessboard. (An inverted chessboard... is a chessboard!)
There is a lot of math involved in this game and you can quite quickly note some less obvious rules like this one. Maybe there are some very nontrivial, but interesting things out there. I'm not good enough in combinatorics to tell... :D
8 moves are sometimes required. If you have a chessboard 3x3 grid with the middle square the wrong color, you have to flip all squares except the middle.
http://imgur.com/f5sryfs