First of all, you might want to know that it isn't really as simple as "We put plants there, now we can start on animals." The introduction of plants would have to be in tandem with the introduction of certain fauna and microbes.
So, here's a step-by-step plan of how I think you should do this:
- You land on Mars, which has been given a habitable atmosphere and oceans, but that's all. Stay in the landing crafts for a while, farming high-density algae and termites. Explore the surroundings.
Assuming the landers can work as habitation complexes for the time being, use waste from the farming to prepare some kind of makeshift soil. Plant some kind of resilient (ideally edible, so it can be used as a food source temporarily) plants in the soil, along with earthworms (Vital) and some insects that don't harm the plants.
Begin to plant more and more plants, but ideally resistant ones. Transgenic plants would also be a good idea. Food is also a priority, so food plants are still good.
This is where the terraforming begins proper. Spread lichens and soil fauna where soil isn't already present. Introduce algae to the oceans, and drill boreholes or coat the ice caps in dark algae to make it warmer. Introduce some kinds of fast-growing trees and other varieties of plants, and breed the smallest vertebrates out in the open.
Now you can start making it look more like a wildlife reserve. Slow-growth trees can be planted, and thaw the cryo-preserved embryos of large animals.
Now, here's what to do with the wildlife:
This is actually quite a lot like Pleistocene Park, a proposed solution to thawing permafrost in Siberia. The project plans to convert tundra into grassland by introducing large megafauna. From Wikipedia:
In present-day Siberia only a few of the former species of megafauna are left, and their population density is extremely low, too low to affect the environment. To reach the desired effects, the density has to be raised artificially by fencing in and concentrating the existing large herbivores. A large variety of species is important as each species affects the environment differently and as the overall stability of the ecosystem increases with the variety of species. Their numbers will be raised by reintroducing species that went locally extinct (e.g., muskoxen). For species that went completely extinct, suitable replacements will be introduced if possible (e.g., wild Bactrian camels for the extinct Pleistocene camels of the genus Paracamelus). As the number of herbivores increases, the enclosure will be expanded.
While this is taking place, the effects will be monitored. This concerns for example the effects on the flora (are the mosses being replaced by grasses, etc.), the effects on the atmosphere (changes in levels of methane, carbon dioxide, water vapor) and the effects on the permafrost.
Finally, once a high density of herbivores over a vast area has been reached, predators larger than the wolves will have to be introduced to keep the megafauna in check
So, basically: herbivores first. Just like in Pleistocene Park, release a few herbivores into an enclosure, expanding that enclosure as their numbers rise. If they overpopulate, you'll have to play predator and shoot a few, sadly.
Then, as the herbivores reach the desired density, slowly begin to introduce large carnivores like wolves, big cats, sharks, etc. Eventually, you'll have a fully functioning ecosystem.
As for what animals could live there, as long as you tailor the environment to their needs, pretty much anything. Like I said, coating the ice caps in dark-coloured algae will significantly increase the temperature; whatever temperature you make it, whatever wildlife that can tolerate can live there.
To get these optimal conditions, however, you'd have to alter the atmosphere from orbital platforms, and somehow seed the planet with oceans from space as well, so that the first landers can begin terraforming.
As long as you do it right, you can give Mars any climate and atmosphere you like. Introduce herbivores first, with heavy human intervention, and then introduce carnivores gradually.