This is a good map! I especially like your rivers: very authentic and believable. They add a lot of life to your map!

I agree with both RobA and landorl: the tool doesn't matter to a great extent, and you are proving your ability by using such a simple program as Paint to such a wonderfully high degree. BUT, when I look at these I think to myself: just thank if this artist was using a program with more power, like GIMP!! What heights he could achieve! You are trying to get to work on a tricycle vs. a car right now, I think. For example, you asked about political maps vs. geographical: with the layers in GIMP you could use the same map to do both. And the "digital" effect you are finding an issue would easily be removed in GIMP. I say definitely get GIMP--it's free, we have great tutorials here on it, and I think you will ultimately love using it!

Your fonts are fine, I think, or perhaps a bit too plain. I understand what you mean about readability, but I would go just an inch further than Arial. (And here's a thread that gives suggestions & examples of fonts.)

You're doing great, and I can't wait to see this updated!!!