I would start with a mid sized intuos, and really dig in to the software. If you enjoy it a lot, you could move up to a cintiq. Cintiqs can allow you to create faster, but many professionals still use the intuos. Do keep in mind that even though the cintiqs cost a lot, they still have some lag with the distance between the pen and the cursor, especially when moving fast.
There are also drawing displays from other companies that are fiairly good from what I have heard. Ipads are also very good. pro models
Used is often going to be your best friend for cheapest though. Just make sure that there aren't any major scratches that you can feel with the pen. (grooves)