Well, "best" is a very relative term, and the programs you've mentioned are pretty different. I would start out with something that's either free or has a free demo before you buy anything. That way, you know what you're getting, and you'll know if it works for you.
Illustrator is a vector program -- that means that it's primarily used for print work, and it works by taking points that you give it for lines and drawing the lines itself based on those points. If you want more info on how vector programs work, see
http://www.sketchpad.net/drawing1.htm .
Paint Shop Pro, like Photoshop (and others), is primarily designed for things like painting and editing photos.
None of the commercial software should have any major bugs in it, and when there are, they should be fixed pretty quickly. For a beginner, I wouldn't recommend jumping right into vector-based programs (so, in other words, probably not Illustrator). Paint Shop Pro would probably be pretty easy to learn, or you can look into some other basic alternatives until you get used to working on the computer --
ArtRage is meant for simulating painting, for example, but also does pen and pencil (and it's free). If you want to try vector-based drawing, check out
Expression 3. It's also free (or should still be; while it says you need to be an existing user to download it on the intro screen, it doesn't seem to care, either when you're downloading or when you're installing). You'll need a .Net passport (from microsoft) to download that one though. I've used both of those a lot, and neither seem to have any significant bugs in them. Of the two, ArtRage is definitely easier to use.
If you find you really like working on the computer, you'll probably also want to get a
Wacom tablet at some point. It lets you draw with a special pen rather than using the mouse. Check out their website for more info on that one. (=
I hope that helps, and if you have any other questions, please ask!