Four alternate ideas for the background:
Players can have pre-selected backgrounds (chosen similarly to picking an avatar, likely in that same area) and one is randomly selected for all players in the lobby to see.
Each outfit comes with it's own background (difficult and time consuming but awesome) and one is randomly selected for all players in the lobby to see.
Ditto on the first but only you see yours
Ditto on the second but only you see your character's