I like the idea of mammoth, woolly rhino and musk-ox riders. And camels, certainly. I think I mentioned Moa-riders before (you know, the now-extinct giant flightless birds from New Zealand), or possibly Giant Dodo's? Continuing the prehistoric (but post-dinosaur) theme, maybe sabre-tooth tigers, similar to the wargs from the LotR films (easy to find figures!). And of course, various types of frogs...
PS: For realism's sake, maybe have mammalian ones from one continent, and reptilian from another?