Basically what you want is a monohedral tesselation (or tiling), that is a coverage of the entire plane (assuming 2d) with a single shape where the tiles do neither overlap nor leave gaps.
There are lots of shapes with which this can be done but when we introduce other constraints, usually orientation should stay the same or they should conform to a natural movement direction, basically only squares and hexagons remain.
Take the triangle for examples (which you might know from the tesselation of 3d objects). To fill the gaps between two triangels another triangle has to be inserted, but flipped upside down. This is obviously a hassle to generate when dealing with sprites for example since a seamless connection is important. Also triangular movement sucks.
The most natural, with regard to movement at least, is the square which happens to be the most frequently used. Hexagons are the next best thing and allow for more direct approach to a higher number of movement directions, i.e. not over the corner movement like 8-way movement on squares does. Usually they are used in more tactical games where the increase in movement is important.
Anyway, if you want to read up more, take a look at http://euler.slu.edu/escher/index.php/Tessellations_by_Polygons.