First, in chess you have an 8x8 board, and only 16 peices, so at worst 16 moves to consider.

This is wrong. You probabably meant "16 pieces to consider moving", but for instance the first move of the game both white and black have 8+8+2+2 moves, and the number of possible moves increases until the midgame resolves itself, where it drops and then increases again as the board clears leaving strong pieces like rooks and queens and bishops a clear run of the board. (An unrestricted queen has at most 7+7+8+6 possible squares that it can move to, an unrestricted horse has 8 squares it can move to, thus if you have a king a queen and a horse on an open board you have (6)+(7+7+8+6)+(8) possible squares you could move to, a lot more than 16 :-).

But your point does have merit. GO does represent a larger search space, but not because of the number of pieces. After all Go pieces dont move once placed.