Create two vehicles, move them on a grid based on user input
Use functions
Having code at the top-level of a module is bad practice as it impairs both reusability and testing: as soon as the module is imported, the code gets executed which is not necessarily what you want.
Instead you should use functions and wrap the remaining top-level code in an if __name__ == '__main__': statement.
Having functions would also mean that you need to stop relying on global variables such as GRID_MAX_X, GRID_MAX_Y, first_vehicle_x or first_vehicle_y. Which is a good thing as currently they make your code tightly coupled. Instead, you should pass those values of interest as parameters to objects or functions.
Bug
Requirements state that:

Vehicles are sent sequentially. If the second vehicle attempts to move to the occupied spot of the first vehicle, the command will be skipped. If any move command makes any of the vehicles move out of the grid, that command will be skipped as well.

You effectively skip the command if the second vehicule tries to move to the position of the first one, but you don't skip it if the move would put the vehicule out of the boundaries of the map. Instead you make the vehicule glide along that boundary.
Also note that you can easily compare the position of the two vehicules using tuple equality (new_x, new_y) != vehicule_one_position and check that a number is within bounds using extended comparisons: 0 &lt;= new_x &lt;= grid_max_x.
Indexables
Strings are iterables and indexables, no need to split them in a list or a tuple. I would however encapsulate changing directions in its own class to better separate concerns and avoid a small amount of repetitions.
eval
There is one saying that eval is evil. It has its uses, but never in such simple cases. Instead, you should know that you can reference functions and methods just by their name so you can build the commands dictionnary in the Vehicule class using
{
    'L': self.turn_left,
    'R': self.turn_right,
    'M': self.move,
}

And be able to do commands[command]() directly, without the need for eval.
Use @property
For simpler data extraction, @property methods can help format them and appear as a simple attribute access. This help make a cleaner design.
Proposed improvements
class Directions:
    &quot;&quot;&quot;Circular buffer of possible directions&quot;&quot;&quot;
    DIRECTIONS = 'NESW'

    def __init__(self, start):
        self.index = self.DIRECTIONS.index(start)

    def next(self):
        self.index = (self.index + 1) % len(self.DIRECTIONS)

    def previous(self):
        self.index = (self.index - 1) % len(self.DIRECTIONS)

    @property
    def current(self):
        return self.DIRECTIONS[self.index]


class Vehicle():
    MOVEMENT = {'N': (0, 1), 'E': (1, 0), 'S': (0, -1), 'W':(-1, 0)}

    def __init__(self, x, y, facing, grid, obstacle):
        self.x = x
        self.y = y
        self.facing = Directions(facing)
        self.grid_width, self.grid_height = grid
        self.obstacle = obstacle

    @property
    def direction(self):
        return self.facing.current

    @property
    def position(self):
        return (self.x, self.y)

    def parse_commands(self, commands):
        action = {
            'L': self.facing.previous,
            'R': self.facing.next,
            'M': self.move,
        }
        for command in commands:
            action[command]()

    def move(self):
        offset_x, offset_y = self.MOVEMENT[self.facing.current]
        x = self.x + offset_x
        y = self.y + offset_y

        if (x, y) != self.obstacle and 0 &lt;= x &lt;= self.grid_width and 0 &lt;= y &lt;= self.grid_height:
            self.x = x
            self.y = y


def setup_and_move_vehicule(grid, obstacle):
    x, y, facing = raw_input().split()
    vehicule = Vehicule(int(x), int(y), facing, grid, obstacle)
    vehicule.parse_commands(raw_input().strip())
    return vehicule.position, vehicule.direction


def main():
    grid = map(int, raw_input().split())
    v1_pos, v1_dir = setup_and_move_vehicule(grid, None)
    v2_pos, v2_dir = setup_and_move_vehicule(grid, v1_pos)
    print v1_pos[0], v1_pos[1], v1_dir
    print v2_pos[0], v2_pos[1], v2_dir


if __name__ == '__main__':
    main()