The Pencil Tool (on the same flyout as Brush Tool) produces aliased marks.
To expand on what Conroy has said, what you describe is a desired feature of the Brush Tool. It makes smooth lines, which require anti-aliasing - (plain and simple) a mixing of the painted color with the background. By setting the Brush Tool to lower Hardness values the "mixed edges" get even larger and more diffuse. The Hardest setting still will make smooth edges, as you have shown.
As Conroy correctly points out, the Pencil Tool is the one that fully colors some pixels while leaving others untouched.
You may find out in the end that, unless you have a very specific need for such hard boundaries, you're not fond of the resultant look of things drawn with the Pencil Tool.