The mammoth called Yula is 39,000 years old and hails from Russia - the shores of the remote Laptev Sea, to be precise. Found in 2010 and now in the hands of the Russian Geographic Society, Yula (a youngster 6 to 9 years old) turned out to have a remarkably preserved brain, showing folds, blood vessels, etc. Paleontologists are ecstatic about having a look at what made the mammoth tick.
Are rhinos more your thing? Darren Naish's Tetrapod Zoology blog explores what we know- and what we think we know. It seems the woolly rhino (Coelodonta antiquitatis), usually depicted as resembling a modern rhino in a mink coat, instead might have had a whiff of musk ox about its stocky, long-furred, humped appearance. Or maybe not - prehistoric artists in France depicted it both ways, and Naish suggests the coat, at least, varied with the seasons. They apparently had low-hanging heads and huge horns, and another British paleontologist envisioned them chomping their way through grasses "like giant furry lawnmowers."
A very large and complete woolly rhino skull was just found in Cambridgeshire in the UK, so that's another piece of evidence under study. Finally, there's another recent find of note: a spear, about 13,000 years old, made of rhino horn. It was found in Siberia and still looks lethal. It's the first known spear of its type and comes from a place where humans were not previously thought to have lived in that era.
The northern plains of old North America and Eurasia must have been very impressive places. While the mammoth-based economy in the movie 10,000 BC is ridiculous (as are occasional claims the mammoth survives to this day - alas, it does not), these were really big lawnmowers.
The mammoth, Mammoth primigenius, on a recent Russian postage stamp.