"I was ending up with a harsh step between color fields that I really didn't like in my hand painting attempts. You painted in multiple layers of similar colors and used what I think was a "soften/blending" tool to smooth it all together in the end."
Actually it sounds like the opacity was interfering here, switch to GIMP and I can help you alot more 
the main thing to remember about your brushes is the opacity amount, pressure amount and the mode its used for - in some parts of the video I used the 'overlay' mode for my brush which blends whatever colour you are using into an existing colour, primarily I stick to blacks and whites as overlay colours.
The only time I used the smudge tool for smoothing, was when I took away the atlas lines around the cheeks, neck and head but left some lines as a guide for the eyes etc.
That final effect was achieved by using the curves feature in GIMP, I find it alot easier to work with rather than using levels to edit colours.
"Even Dark Souls' textures look like they are 16bit to me most of the time"
Thats more noticable on the PC version IMO.
Actually it sounds like the opacity was interfering here, switch to GIMP and I can help you alot more
the main thing to remember about your brushes is the opacity amount, pressure amount and the mode its used for - in some parts of the video I used the 'overlay' mode for my brush which blends whatever colour you are using into an existing colour, primarily I stick to blacks and whites as overlay colours.The only time I used the smudge tool for smoothing, was when I took away the atlas lines around the cheeks, neck and head but left some lines as a guide for the eyes etc.
That final effect was achieved by using the curves feature in GIMP, I find it alot easier to work with rather than using levels to edit colours.
"Even Dark Souls' textures look like they are 16bit to me most of the time"
Thats more noticable on the PC version IMO.