They're right about the size... make sure this map is no bigger than 840x800 pixels... Go to Image -> Image size in the very top top menu. This will bring up a window with a whole lotta numbers.
Make sure all your numbers have the chain symbols, which means that your image remains in proportion. The Check box "Constrain Proportions" needs to be checked to get this.
In the "Document Size" area Resolution ought to be 72 pixels/inch. The Width 840 pixels (see the little menu just to the right of the numbers box). The height 800.
If you map doesn't meet these sizes or smaller, use the crop tool. It's the third tool down on the left column of your Left button menu if you can afford to lose the space. OR just change the numbers in the numbers box of the image size menu and let the "constrain proportions do the work.
Alright,lets talk legends and keys. By the way, we're working with you're A image. Whatever you did to the B image made it save bad and it looks all pixelated. Image A is nice and clear.
You've initially chosen to go with a mini-map in the lower corner, which I think is a real bad idea for what you're trying to accomplish. The map has too many regions for a minimap to work. Plus, you're identifying them by their shields, further confusing the map needlessly. I favor taking a color code style key, of which you can see examples on Pearl Harbor, Third Crusade, Ireland, Africa, ect. This style works best for maps with many different regions.
Minimaps are better for maps with broad regions which can be labeled easily, Such as Greenland, Brazil, Great Lakes, ect. Imagine trying to do Europa, NYC or Chicago with a minimap... I'd be difficult because everything would be crowded. So let's roll with a Color Code style legend.
Right now, let's use the upper left legend. First make a folder over by your layers and Label it "Legend Text." Make sure the folder is highlight and then get the text tool and write out the first region. We'll start with Duchy of Estonia and make our way down. It's nice to have some sort of order int he legend and North to South works great. Make sure the text layer is in the proper folder.
Next we need to figure out how to identify the Duchy of Estonia. This is a Crusades map and you apparently like shields, so lets go with a shield shape. I hope you have the Estonian shield as a separate file, if not get it. Open it up as a new file in cs2 and get your magic wand tool out, 2nd tool down, right column, left side menu. Up top, beneath your file/edit/... menu are a few options: Tolerance helps to determine how picky the wand is going to be in selecting area, the higher the number the less picky it is. I usually keep it around 50. I also like to keep it the "use all layers" check box off. It helps to work with your layers better.
Anyway, select the area around the shield and then go to the Select menu -> Select inverse. You should have the shield selected. Go ahead and hit the delete so you've got the selection in the shape of the shield but not the shield. Go to your main map and click on your color pallet towards the bottom of the left side menu, click the foreground square and it will open the color pallet menu. Move off the menu and you'll get the eye dropper thing, click on the Duchy of Estonia and you'll have the color.
Now go back to your shield and use the paint bucket to make the sheild area the same color as the Duchy of Estonia. Once you've doen that, get your move tool (top right, side menu). and drag the shield from its window to the map window. It's probably too big, so resize it by going to Select -> Transform in the top menu. Make it a little smaller, about the height of you're Duchy of Estonia text in the legend. You can keep proportions by holding down the shift while you resize.
Once its in place, make a folder for it and all other items like it. Label it "Legend shields" and put the shield in the folder. You also should name your layer "Estonian Shield" as well. Now repeat the process for Bishopric of Osel and Wiet, then lithuania, ect.
Once that is done, you should have a nicely organized, clear and concise legend explaining what all the regions are and how much they will be worth (we'll get to that later).
Also, are you using a mac or windows?