Why are you debating about a new software? Photoshop is great and you won't find a better software in terms of power and ease of learning. Illustrator is also great although I often heard that it has a steeper learning curve.
I use photoshop and corel draw. I use corel because that's what I grew up with and many says it is easier to learn than illustrator. I tried illustrator a few times and agree. For tracing I prefer inskcape (a freeware) although corel and adobe have tracing capabilities which some people say are better.
Aside for these, unless you want specialty softwares for rhinestones or something else, you already have the best. So, are you having problems?
I have heard of some digital pen for drawing. Try ask your local computer shop.