I think that a map of some kind would be good for SMP, because then adventurers can map out an area and then share the route with others on the server. They would basically work like picture frames; being a able to place them on a wall for all to see, except left clicking would map all the loaded chunks around you. It would be made out of 9 paper, and holding it in your hand would allow you to see the map (At least the bit visible in your hand) quickly without having to put it on a wall. These would be useful with their navigational assistance and decorational style. Just picture it; a room with a few noble maps hanging on a wall with a crafting table and a few chests below, a torch lighting the whole seen with its eerie glow. Sounds awesome right?
I really don't know how much coding would be needed but if it just checks what each top block is in all of the currently loaded chunks and then puts 1 dot of a certain color on the map I'm sure it wouldn't be that intensive.
I was thinking about how much coding would be needed (Difficulty to implement) and how much memory and such would be taken up by variable textures.
notch already made a map previewer that functions outside the game, i'm pretty sure he could implement one that functions inside the game.