Yeah man, try out GIMP and if you think it is something you are going to dig, pick up a bamboo tablet to paint with. I almost wish I hadn't been using photoshop for 10 years by the time I first tried Gimp. It is a competent program, but by that time I was just too set in my ways with PS.
Also, if you feel OK with dropping a little cash for a more polished product, check out ArtRage. you can get a version of it for around $50 that is an amazing value for the money. It REALLY mimics traditional media really well. Better than Photoshop in some areas.