A recent paper published in PNAS details the earliest member of the elephant family yet found, dating from just 60 million years agO (just five million years after the dinosaur extinction event).
The eritherium would have weighed only about 5kg, with no significant tusks. But it was identified as the earliest (most primitive) member of the Proboscidea order, of which the (three similar species of) elephant is the only survivor.
The specimen was found in Morocco; the author suggests it is indicative of a rapid evolution of a variety of placental mammals (in particular paenungulates), due to favourable ecosystem development in Africa.
To look at the implications, it pays to take some perspective. It was a dinosaur world (the mesozoic era) for about 180 million years, until meteor impact(s) 65 million years ago cleared the decks of all larger animals (and much else). The first true mammals emerged early in the mesozoic; placental mammals (as opposed to egg-layers or marsupials) emerged about 120 mya, but under the domination of dinosaurs remained largely nocturnal and shrew-sized.
According to the study's author Emmanuel Gheerbrant, the discovery "supports an explosive radiation of placental mammals" in the five million years immediately after dinosaur extinction. This is not entirely new, but reinforces what had already been hypothesised.
Of course, all this simply demonstrates the part environment plays in the evolutionary radiation of different species. In their time, dinosaurs effectively shaped the environment for other species. Meteor impact then remodelled the global environment, and mammals no longer needed to compete for resources with - or evade - (non-avian) dinosaurs.
Humans in turn evolved from the primate lineage only over the past four million years. According to Tudge (p492 - 512), the evolution of brain size (and gracility) was in response to environmental factors such as cooling temperatures and scarcity of resources, and the heavier, less brainy hominid species died out.
So we have 180 million years of dinosaur dominance, followed by a real explosion of mammal species in the next 5 million years. Most recently, homonids evolving over 4 million years; brain size grew rapidly from 3 mya to 1 mya; modern H sapiens sapiens first appearing just 100,000 years ago. Evolutionary change and radiation can be slow when environmental factors mitigate against it, and rapid in favourable conditions. (Yet in the case of the emergence of humans, challenges may have propelled evolution rather than holding it back.)
Gheerbrant, E (2009): Paleocene emergence of elephant relatives and the rapid radiation of African ungulates, PNAS 30 June 2009 - abstract here
Tudge, C (2000): The Variety of Life. Oxford University Press, Oxford.
Wikipedia on Placental mammals