> And I am ashamed to admit I haven't read any Greg Egan yet, need to get on that :)
Permutation City is his best-known work, and while some people (including me) enjoy the density of ideas, others find the characterisation weak. I'd start with one of his short story collections, such as Luminous.
Second the short stories. Axiomatic has some great ones too with concepts that really stuck with me.
And if you like that, Phase Space by Stephen Baxter feels very similar.