GIMP is good, you just need to know how to use it. Here I can and will give you lots of help throughout. Just post any questions or send them to me via PM and I can let you know my thoughts on how to do it.
Feudal is good. But this makes the balancing harder to do so you will be in GP longer. Just follow the advice given by the blue guys and they will not let you go wrong. As for hero to L, this is an atrocious idea. Why have two starting territs. Drop the hero ones. You can still have the conditional borders by holding the correct L territ to open them. This will give players an incentive to attack them to open new borders and close other players off.
Graphics. For now, I will leave the title to you to play with. And you do need to play with it. You need to learn GIMP like the rest of us.
Lets play around with the playing board. Here is what I would like you to do and it should give you pretty good results.
Walls. Here is an image for you to look at. I have posted steps for you but you need to adjust things to your liking.
Top picture is step one and so on. Layers used - 3 (Ground, glow and wall layers)
1. Using the pencil in GIMP, you can find a size that suits but do not use the fuzzy ones. You need sharp edges for walls. Draw a line (when you have done a small part of it, you can copy and paste to get it done quicker). The pencil will not allow diagonals but there are none on your map that cannot be made at right angles.
2. When you have drawn all the walls, you can select all and use any texture you want here to fill in the walls. I used the GIMP paper one in the illustration.
3. Now comes the fun part. You need to create another layer under you wall layer (glow layer). Again, select all on the wall layer, go down to the glow layer. Select tab at the top. Grow and feather are what you need. My illustration is grow by 3, feather by 9. (Always this ratio. So a grow of 5 is feather of 15). Fill selection with black. You can change the opacity to make it lighter.
4. Floor layer, just fill with anything for now but make it one thing.
This will get you nice walls that look pretty dam good. Go and look at escape in the main foundry and you will see this over a whole map. There are other ways to do this but this is the quickest one I know.
Here is a place you can go for textures. Just download to your machine and use. All royalty free. Make sure you use royalty free only images.
http://www.cgtextures.com/This guy on youtube is pretty good at explaining things and has lots of videos. Good thing for you to go and watch a few.
http://www.youtube.com/watch?v=E84BNlYvcNk