I read Permutation City a few years ago now.
It's certainly a very interesting book that I'd highly recommend. Greg Egan is very much an "ideas" man though. I find that his narratives while intellectually stimulating sometimes don't translate well to a novel format. I find Egan's short stories to be a delight (check out Axiomatic if you haven't) but his novels can be a real slog if you are not a subject matter expert.
Neal Stephenson writes in the same "genre" but he has a much more approachable style while not sacrificing on any "hard" elements.
My recommendation for anybody who's never read Egan's stuff is to start with his short-stories first.
I'm a huge fan of Egan's work, but his writing definitely has its strengths and weaknesses.
In addition to being an "ideas man", I think his prose is generally excellent. He has a real talent for crafting sentences that are clear, concise, descriptive, and often evocative. (He's mentioned that outside of his writing career, he's a programmer, and I get the sense that any technical documentation he produced would be a joy to read.) It's a testament to his skill that his work is as comprehensible as it is.
The downside is that he has a tendency to write character dialogue the same way he writes everything else. Every sentence is carefully constructed to advance an argument, or to reveal a specific detail about a character's viewpoint. The characters end up feeling less like fully-realized people, and more like mouthpieces in a Socratic dialogue.
I agree with the recommendation to start with his short stories. Of the ones that are legally available online, I'd suggest "Singleton" (http://www.gregegan.net/MISC/SINGLETON/Singleton.html) as a good starting point.
Neal Stephenson writes in the same "genre" but he has a much more approachable style while not sacrificing on any "hard" elements.
My recommendation for anybody who's never read Egan's stuff is to start with his short-stories first.