I’ll make it up to Stross with this one; Glasshouse is strange and brilliant, and it got me started on this whole Strossian jag. I went into it cold, with no plot synopsis or other idea of what to expect, and I recommend experiencing it that way. You’ll see why. Highly recommended for those who, like me, enjoy head-trippy sci-fi.
I adore most of what Stross has written, but he has a nasty tendency to let his love of in-jokes carry away his writing. Glasshouse is the first novel of his I’ve seen where he keeps that in check the whole way through, and as a result it’s the best thing he’s written yet. (Not to say it’s free of winks and nods, but they are under control. It’s no longer targeted solely at the readership of rec.arts.sf.written ;) He’s made it onto my buy-in-hardcover list.
My other favorite is the short story “A Colder War,” which is like The Atrocity Archives, but much tighter and without the three-genres-at-once thing. http://www.infinityplus.co.uk/stories/colderwar.htm