I don't think placing game related files in MyDocumentsMy Documents/My Games/ annoys users, it's pretty much standard to put it there so why don't you do it? Each user can have it's own save games, skins and mods this way and it's easy accessible/mod-able.
However, for larger assets you do want to consider to share them amongst user accounts. I think you have two options:
Users/Public/isn't tied to a specific account and can be used for this.- Store it locally like in a
Data/Mapsfolder within your main game folder.
Apart from that, I think map data should in most cases not be all that large. UnlessMaps should just be a bunch of numbers like ID's and positions so unless it are huge dynamic worlds you are talking aboutit won't really matter to have duplicates on rare occasions stored on the same HD.