Probably most LWers are familiar with it, but Hofstadter's classic "A conversation with Einstein's Brain" is a good read on these same questions.

I am always confused, too, when I think these questions. The only way I can think of solving the puzzles without rejecting computationalism is to reject an ultimate distinction between a computation existing abstractly and a computation being ran, and go in the Tegmarkian direction of a fully Platonic ontology of abstract forms, among them computations, among them us. But since I don't find this believable (gut reaction, which I acknowledge irrational but I can't remedy) I go back in practice to either rejecting computationalism, at least in its strong forms, or assuming there is another solution to the puzzles which I cannot think of.