The problem, as I see it with Stephenson, is that he goes in to such detail that he always needs to build up the world in such a depth that it can make the opening to his books long winded. Any time I have recommended a Stephenson book (and I've read them all, and recommend them all) I warn people to get past page 100, because that's when you will get sucked in to the story. His writing style can be a little unsettling until you get used to it (IMHO), but once you are in there you won't want to put the book down.
As for recommendations - Cryptonomicon, Snowcrash, Diamond Age are all great - the later two are far easier reading but still show the great depths of knowledge and research put in to the books. And once done with those - read the rest.