I would recommend sketchbook pro for freehand sketching. It is not as powerful as photoshop, but the interface is awesome, and the sensitivity of the brushes much better for sketching.
Sketchbook Pro is pretty good, as Yo said the interface is great, and it’s done in a way which does make you feel more like you are sketching than in, say, Photoshop, which is overly utilitarian for sketching.
Corel Painter is good too, pretty easy to get to grips with, slightly more complicated than Sketchbook Pro.
Illustrator is one of my favorite programs, but you can’t really sketch easily in it. I’m not sure of your knowledge, but Illustrator is vector based which means you can resize your work without any pixelation etc.
I’d say check out Sketchbook Pro. It’s quite impressive for such a small and simple program.
Sketchbook Pro interface is really sweet, however, unless things have changed there is no option to “spin the paper”. Sketchbook only allows you to rotate 90 degrees. Which makes you twist and turn your arm in order to get the right position. This could be just me because I’m used to turning my paper alot when sketching.
I like Painter because you can make a hot button on your tablet that will let you spin the page around 360 at any angle to allow you to get the perfect position. Once you get used to it, it makes things a lot quicker.