As you can see in your own gravatar on this site, you can go for a 4x4 field. An even number of cells per side will limit less on the shapes used in the middle, as they are rotated as well.
Offsets could be allowed, if rotated. Offsets that are equal on both dimensions might look more symetrical and could be favoured, but it is not necessary to do so.
You can also rotate differently, by 180°, loosing some symmetry, but as you can see here, it does give you interesting identicons.
Of course you could pick more then two colors. From an estetical standpoint, choose wisely from colors within a certain scheme. Maybe some effects like making the colors lighter or darker towards the edges gradually would look very interesting.
Do I understand you correctly that you would seed the randomizer with the MD5 value of the users email address and thus be able to recalculate his gravatar on the fly? No need then to have him create an account.