I think your question is less "how do I get started" and more "how do I progress?" or "how do I make these look better?" Because you have gotten started, in fact you've gotten further than some people know how to get.
You could hire me or someone else on the forums if you want a professional quality map. If you want to make them yourself, I would do the following:
-Learn some color theory so you can pick colors that match well. I would call the choice of the bright red on blue "garish", and myself, I would have probably gone with white text with a black stroke. Can never go too wrong with that.
-Create your map with layers, so that you can create some form of shading instead of solid color blocks. If you like the mono-color blocks, I would instead use a vector program because it will create smoother lines.
-I don't know what you're using but there's a free Photoshop clone called Photopea and it has the ability to put strokes on text, so there's really no excuse to not set up text with an outline for increased readability. I assume you're using a program without layers which is preventing you from backtracking and editing. Creating a file that you can go back and edit as you develop is key to getting a good looking map, I think, unless you're really good at laying out information visually by eye.
-You'll want to check "anti-aliasing" on your lines so they're not as jagged if you keep using a raster based program.
-Keep in mind distinct contrast between colors. Not just difference between colors, but in saturation and luminosity. For distinction, colors ought to vary in a couple of different manners. I would start by selecting a couple of colors that represent the nations and then pair those colors with a neutral which distinctly contrasts for the lineart and inner details. I tend to choose to focus my coloring on the political regions OR on a realistic sort of color, not both. So if I'm doing blue water and green land / land coloration, I would choose to have neutral text (like black with a white stroke or white with a black stroke). If I'm doing a political map, I'm going to not only put color where the political regions are, but associate that same color with the text for the region ideally, so that there's a visual link. And I will not be using that color for any land design, it's exclusively focused on being that political symbolic association. Or if I am using it in the design it's sparing and intentional.
-There are a couple of different types of ratios which help to mathematically work out the balance. The rule of thirds, fi, rules of kerning for text, items in clusters that are big, medium, then small–and you start by plotting big regions and working inwards to the small details, never the other way around.
-Keep in mind standard print dimensions if you want it to go into a novel. The dimensions you've designed these for would not print well.
-I look at maps. I bought an atlas for fun. A globe for fun. I look at Google Earth. I look at satellite images. I look at historical maps. Seriously, just look at tons of maps and try work out how they may have constructed it.
I honestly, when I started, would have had no idea how i do my maps now. The work I do is so far beyond what I started with. So it really doesn't matter if you've done fifty works in progress and they still look like ****, just keep plugging along and drawing them over and over and over again and eventually you'll get better. That's how pretty much all skills work and maps are no different.
I have this faint memory of being like, 8 or so, and reading a mystery novel with a map in it and being like, "I want to be the person who does that." And now I am. So really all you need is to love fantasy maps in novels and be stubborn enough to keep drawing WIPs until you get to one you can stand. I don't think it's the easiest form of graphic design to be good at, but there's plenty of programs to facilitate easy cheap fancy maps too, like Wonderdraft. If you feel stuck by your program, you might look into one of the programs for cartography specifically. That said, I use Manga Studio / Clip Studio Paint for almost everything, so I don't think it's the program, any program that can create layers, selection masks, stroke outlines, and text is all you need. A vector program might be nice depending on your desired outcome. Some people use Qgis, which is also free, and designed for mapping, though with a steep learning curve–I've used it a couple of times for real world map outcomes.