Excellent sci-fi which you may like if you're a fan of Stephenson can be found in Charles Stross. His first book, Singularity Sky, is fun but a bit unpolished - later stuff gets much better, and I thought Iron Sunrise which I just finished a couple of days ago was pretty stellar.
I cannot recommend Iain M. Banks strongly enough (same person as Iain Banks, but the M. is included on his sci-fi stuff). I couldn't get into Feersum Endjinn but I absolutely love, love, love The Culture novels, it contains two of my favorite books ever (Excession and Use of Weapons) and they're all pretty great. I wouldn't start with the first book though, Consider Phlebas is a real bastard to get into without knowing the universe; The Player of Games is generally regarded as the best one to start with.
Of course, you could look to a lot of older authors here as well. I'm currently reading The Drowned World by J. G. Ballard, and it's gripping stuff. Pohl wrote good works, I'm especially a fan of The Coming of the Quantum Cats. Obviously there's the Big Three - Asimov, Clarke, and Heinlein, and you can really choose damn near anything by any of them and you'll strike gold. (I would especially recommend Rendesvous with Rama by Clarke, it's one of the best instances of really creating a sense of 'alienness' I've ever come across.) I would also stick Brian Aldiss into a list of the great masters of science fiction, especially in light of his insufficiently well-known and well-regarded Helliconia books.
Oh, and if you can get Before the Golden Age, edited by Asimov, do so. It's a collection of early sci-fi short stories; some are okay, a few are good, and one or two are real finds (I'm thinking of Charles R. Tanner's Tumithak stories here specifically).
I'll second Aaron's suggestion of Le Guin. I'm a big fan of her Earthsea novels. Also consider Kim Stanley Robinson's Mars trilogy, which I've not yet got around to reading but have heard great things about.