[The Fifth Horseman]

Personally I'd suggest C++, but that might just be me.

Also note that what you described is anything but simple. The more freedom the player has, the more things you have to account for in the game engine.
World map... well, you won't have anything in the way of graphics to start with, except what you code yourself.

First see if you can make an almost completely linear game. Then work on expanding it.