Court of the Crimson Kings by S.M. Stirling. A good friend game me a copy when I was in hospital a couple of years ago, and it is one of the best pieces of SF I have every read. For our purposes, you must have a look at the Martian biotechnology. Absolutely 1st rate; an alien species with this sort of technology is a must-have.
Click for some sample chapters!