I´m sorry that I don´t have time to help very much these days.
When I´m looking at the location backgrounds today, I´d say they should get a complete overhaul, at least most of them. And not just a bit by adding some trappings. Besides the outdated size there are some perspective, lighting and style issues that should be fixed if possible.
Don´t be scared now, starting illustrators out there: Sometimes it´s even easier to rework the whole thing than to add something in someone else´s style. I´m pretty sure you´ll have many ideas to improve these old sceneries.
Whoever will dare to try it: Maybe I can help a bit by giving advice if you need (via e-mail or in the project forum).
I´d say the to-be-reworked locations should have a target size of 1920x1080 if possible.
Ah, and about composition: Well, if it´s possible to chose the position of the added background part freely (depending on the location), that should be no problem (like 'a bit on the left side, a bit on the right side...).