uh.. what the hell does "difficulty" refer to? other than perhaps something really abstract like item count or geometry? but I can't really deduce anything like that immediately.
"Complexity", as in how difficult the layout is to adapt to or memorize, etc. or if the map has many elements that make it more difficult or dangerous to play on.
It's not a perfect system though, and I've seen some silly tags for the official maps. For example, "Canned Heat" and "Theatre of Pain" are both "Medium"-sized maps.
a couple of questions/corrections/clarifications as well:
spacecamp should be QL and not really Q3, surely?
house of decay should be Q3DC and not Q3TA?
eyetoeye - QW/Q3C?
ztn should really be Quake?
aero QW?
devilish--is this really a Q3 custom or QL?
concretepalace--Q3 custom or QL?
beyond reality--technically Q3A?
focalpoint--really Q3 custom or QL?
not specified: seamsandbolts, jumpwerkz, cliffside