I think you may be somewhat confused about Eliezer's terminology. You say:

You may see the unacknowledged dualism to which I refer, in the phrase "how an algorithm feels from inside". This implies that the facts about a sentient computer or sentient brain consist of (1) all the physical facts (locations of particles, or whatever the ultimate physical properties are) (2) "how it feels" to be the entity.

But the original article does not propose any kind of a dualism. Instead (IMO), it attempts to expose certain mental biases inherent to all humans, which are caused by the specific ways in which our neural hardware is configured: "Because we don't instinctively see our intuitions as "intuitions", we just see them as the world".

You say that...

People generally notice at some point that the "color feelings" don't exist on the physical side.

But people "generally notice" a lot of things, including the existence of gods and demons, and the shape of the Earth, which is flat. Just because people notice something, doesn't mean it's there (but it doesn't mean it's not there, either). You go on to say that materialists are...

...finding consciousness an unfathomable mystery which always eludes analysis...

But this just isn't true. We know a lot (though not everything) about how our consciousness operates; in fact, we can even observe some of it happening in real time under fMRI scans. Sure, some philosophers might wax poetic about the grand mystery of consciousness, but they are the same kinds of people who waxed poetic about the grand mystery of the heavens before Newtonian Mechanics was discovered.

Thus, I'm not convinced that...

...there absolutely has to be color on the "feeling side" as well...

...assuming of course that by "feeling side" you mean something distinct from brain-states. I could be wrong, of course; but since you are making the positive proposition about the existence of qualia, the burden of proof is on you.