Deluxe Paint and Personal Paint both have grids. You activate it by pressing 'g'. You have to setup the steps ofcourse.
Also, if you use the magnifier ('m'), there is an option in PPaint at least, to switch on a visible grid. Just click on the grid symbol just above the colour palette, next to the fore/back pen indicator(selector).
Edit
Wait, this actually selects the colour of the grid. i think the switch is in the corner of the magnifier's window, bottom right.
In DPaint, the grid symbol is above the magnifier symbol, click it with right mouse button to change the grid steps.