Why do the two hemispheres of the brain control the opposite sides of the body?
Just to get the ball rolling here.  This particular aspect of brain evolution is very old. The cross wiring of the hemispheres of the brain seems to be as old as the right and left hemispheres itself.  It predates lizards - i.e. hundreds of millions of years ago. It  possibly predates right/left dominance and the organ asymmetry which puts the heart on the left side of the body. 

Digging back deeper, we can see that worms have bilateral brain structure, but as noted in the comments below, the nervous systems do not cross.  I would guess that this means that the phenomenon appears sometime before lizards - putting the development having been done by the early Carboniferous period when the first animals came to the land and the first reptiles appears, which is the perhaps 350 million years ago.  

Echinoderms (like starfish) are 'missing links' in bilateral symmetry as their larval stage has bilateral symmetry even though the adult has radial symmetry.  Such wiring may be so embedded in the way most animal body plans develop that it hasn't changed in evolutionary history. If that is related to other animals trait, it could be a billion years ago. Some argue this is not the case.  

One might guess that the cross over of neurons in brain control is good for integrating the signals from both sides of the organism. There are quite a few theories.