I've always had a little trouble defining RPG's for myself too. It was always a game where there was a group of people that had to some sort of quest. Along the way they have some sort of an adventure and I think this still stands as the basis for what an RPG is. There doesn't need to be that major bad guy, there doesn't need to be any fighting, there doesn't need to be any character development.
Discovering new maps is kind of necessary, but I generally don't think it defines an RPG because basically if you have a game where your characters are going some place, the next area/map is always going to be new, no matter what kind of game you are making. Same thing really for the world. The maps and the world in general in which you set your game make the game more interesting and unique, but again I don't consider them to define what an RPG is.
The story I guess leans more towards defining your game. I mean your game could be about a group people travelling to another region to try and prevent another war from breaking out. It's basic and you can't tell what kind of game this is, but it's an accumulation of all the extra details you put into your game. Are the group army men? I'd lean more towards an Action game. Are they elves battling orcs? Probably a Fantasy.
Now the difference between Fantasy and RPG (to me anyways) is always tough and rather like splitting hairs. Fantasy has "Fantasy creatures", your typical groups of Elves, Orcs, Ogres, Humans, Dragons, Dwarves, and maybe some other creatures thrown in there. RPG's have weird or made-up creatures and/or fantasy creatures like Slimes, Demons, Behemoths, and Elemental beings. The difference between fighting styles also plays a part. If the battle is real time, ie. you move your character around the battle field freely, tapping buttons to swing weapons and the ability to attack any enemy you see fit, I count this as a Fantasy-Adventure. If the battle system is a static screen and you choose your characters' actions, well I consider this an RPG. Character development, at least in the personal sense, does make the game more of an RPG than a Fantasy game too, but both games can have character progression/development in the fighting sense of the definition.