With the news circulating about Alastair Reynolds' major new publishing deal, I've noticed that there's been a fair bit of interest circulating on forums by people who haven't tried reading him before and want to know where to start.
For the stand-alones, it's pretty straightforward. The novels Century Rain, Pushing Ice, House of Suns and the forthcoming Terminal World are all set in their own universes with no link to each other or to his main series. The short story collection Zima Blue also consists of stand-alone stories or stories that are linked to one another, but nothing outside the collection. Out of all of these I would strongly recommend Pushing Ice as a solid starting point for its 'Big Dumb Object' SF style and its use of relativistic science, with some excellent characters and a solid story also present. Century Rain, whilst slightly weaker, does showcase Reynolds' interest in out-of-the-box thinking and his interest in noir thrillers.
The reading order for Reynolds' Revelation Space universe stories is altogether more complex, with the novels overlapping with the short stories (collected in Galactic North) and the two novellas (collected in Diamond Dogs, Turquoise Days).
This is the chronological order for the short stories, novels and novellas:
'Great Wall of Mars' *
'A Spy in Europa' *
The Prefect'Dilation Sleep' *
'Diamond Dogs' **
'Turquoise Days' **
'Grafenwalder's Bestiary' *
'Galactic North' *
* Story in Galactic North
** Novella in Diamond Dogs, Turquoise Days
Whether this is the best reading order for the books or not is debatable. I think it mostly works, although The Prefect may have more impact if read after the trilogy (Revelation Space, Redemption Ark, Absolution Gap) when the reader is more familiar with the Conjoiner and Ultra factions. Also 'Weather' contains the answer to a major mystery from the trilogy about the Conjoiner lighthugger drives and may benefit from being read later on.
What I would say is that 'Great Wall of Mars' and 'Glacial' should definitely be read before the trilogy, as they introduce characters who otherwise show up out of nowhere in Redemption Ark, and 'Galactic North' (the story) should be read after everything else as it explains the (somewhat puzzling) ending to Absolution Gap and puts something of a full stop on the whole series and story. Chasm City can be read before or after the trilogy, but benefits much more from being read before as some of its characters play a role in Revelation Space.