Krita - FREE, Advanced, multiplatform. Very powerful.
Obviously being free is a great benefit of using this application. But more importantly it's actually an amazing drawing program. I use Krita when I want to do a more traditional painting style. So don't use it for line art or illustrations. But whenever I feel like I want to do a lot of work with colors or that needs a lot of sophisticated brushes then I use Krita.
Because Krita is free and open source it is also the app I use when I am testing tablets. For example when I am trying to determine how good a tablet or pen works with pressure I'm always testing that with Krita.
It is a more complicated application, so I'm not sure it would be the best for a beginner.