more intimidating is the Andrewsarchus, the largest land mammalian predator. clocking in at "19 feet long, and standing 8 feet tall at the shoulder. its skull alone is 3 feet long and 2 feet wide... its teeth are very large and sharp... it seems to have been an ancestor of modern whales."
I like how they talk about "skull alone." The only known specimen of Andrewsarchus is a skull.
Andrewsarchus is generally thought to be part of a group called mesonychids, a group from the Paleocene to Oligocene of the northern hemisphere. Most of the mesonychids were more in the size range of domestic dogs. One of the most interesting things about mesonychids is that they combined two unusual features: hooves on their feet (or at least flattened nails rather than claws) and teeth indicating a carnivorous to omnivorous diet. Andrewsarchus was actually thought to be more on the omnivorous end, kind of like a giant bear.
As far as their relations to whales, that idea only recently has been dealt a number of blows. First, DNA sequences placed hippos as the closest relatives of whales, which definitely would remove mesonychids from the family tree. Paleontologists were (and many still are) skeptical, but, within the last couple of years, fossils were discovered of early terrestrial whales with complete hind limbs, and their ankles clearly demonstrate an affinity to the artiodactyls ("even-toed" hoofed mammals) that include cows, sheep, antelopes, giraffes, deer, pigs, and hippos. Thus, many paleontologists are more willing to accept the whale-hippo relationship now.
Getting back to the original intention of the thread, there are lots of prehistoric creatures that could be fit into a campaign. Most of them could simply be slotted into an existing dire template. For instance, Archaeotherium is a big ugly pig-like creature that could probably just use the stats for a dire boar. I think MM2 expanded the list of prehistoric creatures; IIRC, they had the 18 foot tall hornless rhino, Baluchitherium (also known as Indricotherium or Paraceratherium), as well as a giant ground sloth. How about glyptodonts, giant grazing tank-like armadillo relatives?
Since marsupials have been mentioned, I'd put my vote in for Diprotodon, essentially a rhino-sized wombat. And how about giant flightless birds, like the carnivorous Phorusrhacos (is that in a book already?) or Diatryma, or the simply very large elephant birds or the simply tall moas? There are indeed lots of choices.
--Axe