I use a Wacom Intuos 4 tablet; one of the nice things about it is that it comes with a variety of tips that are meant to reproduce the tactile feel of various instruments, including pencils. The "pencil" nibs (light grey) tend to feel more like the harder lead pencils, but the range of tips means you should be able to find something to your liking (right now I'm using the standard black tips only because it's a nice compromise between "mushy" and "chalk on a chalkboard").
I would go to a local dealer (not sure where you are) and try them out, specifically with the various tips. The Intuos 4 is also pressure-sensitive, and I know you can customize the sensitivity (again, right now I'm using the default sensitivity because it fits in to most of the tasks I'm doing - vector layout, painting opacity masks, pen tool, etc.).
BTW, if the local sales rep can't find them, the extra tips are hidden in the stand for the pen. Unscrew the stand and you'll see them there. The removal tool is right in the center; it looks like a little ring. Swapping out tips is really, really simple, so if you end up with two different tips you like it's not a big deal to swap them out. Or, if you win the lottery, you could buy a second pen and put a different tip in it.