In class we talked briefly about anisogamy - a condition where gametes are dissimilar, often one being small and motile while the other is very large and lacks motility (sometimes known as oogamy). Understanding why this occurred and the mechanisms behind it would essentially explain why gender exists - and why it has taken on the forms that we recognize today.
There are actually many theories which attempt to provide a mechanism for the evolution of anisogamy. One theory suggests that there are selection pressures which favor high gamete encounter rates (more encounters = more offspring = higher chance of passing genes on to next generation, etc). It turns out that encounter rates are maximized between gametes when one gamete becomes smaller and one larger - an example of disruptive selection, favoring both large and small gametes but not those of intermediate size.
Another argument that John brought to my attention is one that postulates that anisogamy is related to the origin of our organelles by endosymbiosis. Other arguments wrestle with ideas such as a possible pathogenic selection pressure for anisogamy, the uni-parental inheritance of mitochondria as a result of some selective pressure for this situation which may have also been a major driver to anisogamy, and some theories that simply attribute the evolution of anisogamy to the higher fitness of a larger zygote that would be formed from a larger egg.
When you get down to the core of things, it's actually pretty funny how one might truly define gender. One could simply say that the only difference between one gender and the other is found in regards to the motility of their gametes - one of us "likes" to swim around while the other "prefers" a more stationary lifestyle - but I really shouldn't attempt to personify gametes. While many people like to form a firm distinction in regards to what it means to be male and female, the true fundamental differences aren't really that divisive.
Here are some links if you want to look into this stuff further: