Digital painting in Photoshop with image dimensions of 5000+ pixels and a dozen or so layers eats RAM up pretty quick. 6GB on my x58 rig couldn't handle it. I recently plugged in 24GB and things are running much better.
Unfortunately large brush sizes can still lag a lot. Particularly when spacing is set to a very low value, or while using the mixer brush. Ram doesn't help here, and I don't know if a CPU or GPU upgrade would help much with this or not. Maybe nothing helps here. No tech sites offer any suggestions. Even Adobe themselves make no mention of how to speed up brushes. Their advice ends with "more RAM for bigger files, and a GPU only helps with a handful of filter effects".
Our Photoshop benchmarks would suggest it is CPU power, what CPU are you using?