I'm going to reserve this space for my progress in phase I (until feedback).
EDIT 1:
I always start with some brainstorming ideas. While I never write them down, I think that for this workshop it's good to share them.
some initial thoughts after reading the script:
- why are my trees/plants in pots? - why doesn't anything grow naturally? - Hmm, imagine this being a science fiction background with some plants under glass domes. Maybe they are connected to the oxygen system. But how are you going to get in to get the fruit? - Glass cutter...? - I could also use a force-field and the puzzle is to turn it off. What happens to the tree? - I'm pretty sure it's going to die and people aren't going to be happy about that.
- The fruit should be used in the jail. Maybe it's a good idea to put the jail somewhere in the background so the player is subtly reminded of it.
- Trin is proud...his office should reflect this. Proud shapes, a little more Baroque then the other buildings. Gold is good. He wants his office to reflect his stature...
many of the brainstorming ideas will be scrapped, others will change, and new ones will come...just some things to get me going (and if it's useful to you, just borrow some of them).
EDIT 2:
I haven't started on the actual background yet, but - in preparation - I'm trying to figure out the world I want to create. One thing I like to do is to work from the characters. So I created two very rough characters to get me going with the atmosphere and stuff. It's good to have a few extra days to do that.
I decided that this story called for a female lead that I've dubbed Charee. She's going to be a full-blown adventurer straight off, I feel that giving her an origin story will diminish her character. So it's more Indiana Jones, and less Young Indiana Jones. She has no problem pummeling her fist into someone's face if the feels it helps her progress, and if she can't pick a lock then kicking the door down is just as effective. She doesn't believe in terms like
feminism or
strong independent woman, but rather thinks that everyone - man or women - should be able to rely on themselves (but should not be afraid to rely on others). She doesn't do bright colours, princesses or rainbows; so I'm going to use a desaturated palette for most of the image to reflect this.

Charee was hired to deliver a young girl/mage (less magic, more StarWars' the Force) to the capital city (it's all on a single planet). The way I envision the fictional game you would have three playable characters: Charee, the young girl, and a flamboyant con-man. Since the backgrounds will reflect their particular outlook on life, the same location (and characters) will look slightly different when playing with a different character (the girl for example sees only the good and is easily impressed. She does not see the dangers in the world, the scene is just a little bit more colourfull, and the office of the harbor master just a little more imposing in shapes and decoration).
Also, if Trin has deer-like features, his office will probably be influenced by Nordic architecture. And considering the amount of stuff and the fact that it's a 'fairly wide open space' I might have to think about a scrollable background.
As I said, this is just me creating a world, and getting a feel for the story I want to tell (that this background is going to be just a small part of).
EDIT 3:
Character-size is an important factor when designing a background for an adventure game. I personally tend to design my backgrounds so very little character-scaling is needed (basically that means that the line of action is mostly within a single (fake) 2D plane); for my personal taste, the character can scale between scenes but preferably not within a scene. Even during the thumbnail-phase it is important to take this into account.
I took a look at some of the classics:

and noticed that for me the sweetspot for the character-height is somewhere around 35% of the scene-height. Below that I feel the character is getting to small, and above I feel the scene is too cramped (in reality I never had a problem with Roger being small or MI3 being cramped, but it's just the feel I get from these images). Just something to take into account early on to make sure the scene will work inside your game.
EDIT 4: First Rough

EDIT 5: Second Pass

EDIT 6: Lighting my Scene

EDIT 7: Re-evaluating my design

-- Continued in
Stage II --