ok... You are using layers in photoshop right? If not... you're in trouble.
Take a look at the Hungary thread, linked here: viewtopic.php?f=63&t=108937&start=15
There's a lot of good discussion about how to work in layers and make your borders and colors seem smooth. Before you press on, I think you need a presentable image.
The first thing to do is fix those rough borders.
Create a new layer and label it borders.
Zoom in to about %600.
Select the brush tool, black color and size 3 px.
Systematically trace over the borders. It doesn't have to be exact but close will do. You will ultimately be deleting your original image, so don't worry about it.
Once you've done that create a new layer and label it rivers.
Do the exact same as the above with a bluish color of your choice.
Trace over the rivers.
One of the big problems with this map, imo, is that the tri-colors of the empires contrast with each other too much. Make the Ottoman Empire various shades of red, make the Austrian's various shades of white, make Hungary shades of Green. (or colors of your choice). That way the regions have some sort of graphical unity.
Next, you're going to want to apply these colors...
Create a new Layer and label it Ottoman Hungary.
Get your brush tool and change the color to something like burgundy.
Increase the size of the brush to about 20.
Color in the regions that comprise Ottoman Hungary.
Shrink the brush to maybe a 5 px and get in the little nooks and crannies of the border.
When you're done you should have a much clearer map of Ottoman Hungary.
Repeat the above step for all your regions, including the sea. When you're done, you'll have a better looking map.
But obviously label the territories whatever it is that you want to label them. Ottoman Hungary probably isn't appropriate here
While I suggested you fix the legend before, I'm going to say lets hold on that a second. When you make the borders you're going to learn the basics of the brush to help make those legends look nice. So yeah, fix the borders and the colors. Skip the dots for now, you'll add those on another layer later.
Make sure you're resolution is 72 and that you're working on the large map (I usually go 800 x 800 pixels for this size).
Regarding your legend, don't mess around with anything complex on that just yet. Box it in and here's how.
Go to the shape icon and hold it down so you get a choice menu, select box.
Create a new layer that is higher on the list than all your other layers, name it "Legend".
Draw a box around your legend information.
Select the Brush tool and make sure your size is 3 px and that your foreground color is black and background color is white.
Select the Pen tool (right next to the shape tool) and move up to the top menu. To your left there are 3 boxes with pen tool diagrams on them, select the middle one. Go down to the box you drew and right click on it.
Select "Stroke Path" and this will bring up a menu, make sure brush is selected and hit ok.
Viola, you have a box. Now right click the box again and select "Fill shape." Make sure in the next menu the background color is selected and hit ok.
Finally, right click again on the box and select delete path.
You're text should be gone now but that's ok. Go over to your layer menu and select the folder icon (at the bottom, third button on the left, looks like a little folder) Name your folder "Legend Text." and put all text that is in your legend in it (standard drag and drop).
Once you've done that move the folder above the "Legend" folder and you're text should be back.
Repeat the same for your legend graphics.
It seems like a lot to do, but it's not really. Maybe an hour of your time and you're map will be better for it. Once you've got smooth borders and your land colors don't fade next to the borders, you'll be in good shape. We'll hit your minimap next once you get your borders and colors right.