I outlined a possible map idea
hereAs for other ideas:
An island, like Lost. Might be difficult to make foliage appropriate for this idea though.
Oil Rig (as said earlier).
Interior of a mall
Space Station (bonus points for zero gravity and a way to navigate within it!)
Temple/Dungeon/Cave system interior
Port (spinoff of the ship map; ship is docked at a port which is cordoned off because of suspected terrorist activity. Interior of ship would be cut down and bricks spent on a port)