Red Mars (and its followups, Green Mars and Blue Mars) is the best treatment in fiction I know of regarding the terraforming of Mars.
Your objectives for terraforming are primarily to generate an atmosphere. to introduce something that will start making oxygen, while being able to handle the cold and dry and radiation. Both Red Mars and other authorities suggest that lichens are the way to go, and could be adapted to Mars' hostile environment in short order. Lichens should be distributed widely over the planet, where they will start he process of both generating oxygen.
The next priority, is some type of decomposer to start turning the dead bits of lichen into usable soil. This would be some combination of fungus and bacteria.
After that, you have to wait until conditions get better. This would take forever by its own; you would probably want to hit the planet with a few comets full of useful volatiles like carbon dioxide (to help the plants, provide pressure, and cause a greenhouse effect), water (also important for the greenhouse effect) and nitrogen compounds (to start a nitrogen cycle). Eventually, the combination of heat from impacts and greenhouse effect will start melting the water and carbon dioxide ice caps.
Once the planet has some more water, nitrogen, and atmospheric pressure, things would be improved. Vascular plants could survive once carbon dioxide partial pressure gets high enough and water is available. Plants with deep roots, particularly trees, will be important to extract useful minerals from deep in the soil and add them to the available bio-cycles. They will be much more efficient oxygen generators than lichen. Also, if enough liquid water can form lakes or oceans, then various plankton will also contribute a lot of oxygen.
That's the moral of the story. I don't see any reason to introduce plants to the planet that aren't wheat, and animals that aren't cows. Why go through all the effort to remake the planet, if you don't remake it for us?
Edit for hard-science:
According to Kass and Yung, 1995, solar wind induced sputtering on Mars could potentially remove 2.4e24 molecules of CO$_2$ and 8.6e25 molecules of H$_2$0 per second. This amounts of 6kg and 93kg per second, respetively.
This may seem like a lot of materials, however, the Earth's atmosphere is 5.15e18 kg. The ratio Mars:Earth surface area is 0.53, so an Earth-like Martian atmosphere might have mass 1.46e18 kg. For this mass, the half-life at the above rates of sputtering are 500 million years for $H_20$, and 7.3 billion years for CO$_2$.
Of course, the Martian atmosphere will lose less mass as its density goes down. Instead of losing 6 kg of CO$_2$ a second, according to Edberg et al, 2010, quoting Barabash et al, 2009 (which I do not have access to), the actual loss rate in the Martian atmosphere is 0.01-1 kg per second, depending on solar conditions as discussed in their paper. But with a nice full atmosphere, the higher rates of sputtering losses would be observed.
The question then becomes, if the CO$_2$ half-life is 7.2 billion years, then how did Mars lose its atmosphere? This is the purpose of the Kass and Yang paper. The Sun's UV output was higher in the past, even as its overall luminosity was lower. According to their paper, 3.5 Gyr ago, the UV incidence on Mars was six times higher than present, and 2.5 Gyr ago, it was 3 times higher. At these higher UV exposures, the loss rate of CO$_2$ was about three and two orders of magnitude higher than current, respectively. The conclusion of their paper is that, integrated over 4.5 billion years, Mars has lost about 3 bar of CO$_2$.
However, for our purposes starting in the current day, that loss will not be repeated because the sun's ability to strip Mars' atmosphere is significantly reduced.
If we added an atmosphere to Mars, it would take on the scale of billions of years for it to be removed. If we can add an atmosphere in thousands of years, there will be no problem retaining it.