Look to older, popular multiplayer games for inspiratioin, I say. Counter Strike was amazingly popular, and had literally thousands of custom maps, some of which sucked, but many of which stood out as shining examples of creativity.
Part of what made many of those maps awesome was the lack of restraint felt by the map makers. CS was set in the 90's, and its characters, gameplay, and overall theme reflected "terrorist vs counter terrorist". Despite this, there were created maps that defied the game's theme; some defied reason and physics, too. I point specifically to the surf maps--I think that's what they're called--in which players hurtled down giant slides. The de_rats maps also were rather original, placing the proportionately rat-sized players in massive kitchens, bedrooms, or living rooms.
tl;dr: don't be feel like you have to conform to the medieval theme with your map. Let nothing restrict your creativity.
-Perhaps a de_rats esque map.
-A copy of two_rooms. There are two rooms, each just large enough to hold a full team of people (for when they spawn). Separating the two teams is a single, open doorway. Let the slaughter commence!
-As PhantomZero suggests, please god don't just make another shitty city or village map.