tbh drawing originally in any paint program with a mouse is really hard, because you can't control pen pressure, or draw on an image, which is really limiting.
Given that, though, a pixel based program might do you more good. There are several well done illustrations that use pixels, and since it isn't reliant on stuff like brush strokes I think it would be a lot easier than trying to draw with photoshop. You could also try doing something in illustrator with the pen tool, or something. Or, if you don't have any other options, yeah, you could use photoshop and do some of the stuff like Fate was doing before he got his tablet.
However if you're better at sketching and that sort of stuff then I'd stick with doing your work on paper then scanning it in and working from there.