I think a minimap would be a good idea, especially for finding npcs and stuff. The map is big enough to warrant one. Only thing to consider there is how much you show; do you show items, less important npcs, etc.
You could alternatively a map you pull up (say press [TAB]) that shows where you've visited and what was there. Could also have a pointer appear in the game when you are near a key NPC. Might be a pain to implement is the only thing.
Choosing any/all of the above would add to your game I think.
Hope this helps. Glad you found my feedback useful!