I would add Permutation City. It's about: what's it like to be a digital person in a virtual world? What are the psychological effects of knowing that you're virtual; how do you experience time passing; what are the social implications of changing your appearance at whim, etc.
And, how do different interpretations of data compete to become "real"? For example, if you look at it one way it's a city, another way it's a collection of data cells to be colonized, etc.
Um, hard sci-fi? Some handwavy "upload person to computer" stuff and then "we'll just rearrange the universe over here, don't mind us". I did read it a long time ago, but I don't remember anything that specific in it.
Permutation City is definitely hard sci-fi, albeit less hard than most of Egan's work. Ignoring the "uploading" (it not being the central point of the story, and this not being the place to have that debate), his "dust theory" is very well grounded. That's not to say that I believe it (or that he does, see http://www.gregegan.net/PERMUTATION/FAQ/FAQ.html), but that doesn't automatically qualify it as "magic" either.