I second Diaspora; his vivid description of artificial intelligence is worth the read by itself.

Egan's stuff divides evenly into near-future and distant future science fiction; the distant future stuff tends to be very abstract. His latest novel, Zendegi, is a very near-future setting, and coincidentally is a more accessible read than most of his other stuff. I'd recommend it to start with.

I wasn't too keen on Zendegi. About a third of it is how a revolution could happy in Iran next year, and seemed a bit too influenced by the Iranian presidential election protests. I was also annoyed at how it wasn't as hard sf as his other books.