Checking where/if another creature lies in a creature's field of view
In this case, you should divide your world into a 2D grid, where each grid cell is at least as large as your viewing distance. Lets say that the grid has \$k\$ cells. Then, in each step of the iteration you place each creature into its appropriate gridcell \$(O(n))\$, then for each cell you iterate over the creatures in it, and check it against every creature in the up to 9 closest cells \$(O(\frac{9n^2}{k}))\$.

This is still not perfect, but it could provide a significant speedup if you have a lot of creatures, and if your viewing distance is small compared to the size of your world. This would imply that you can make \$k\$ large, and thus you could make your algorithm 10-1000 times faster depending on your situation.

Another thing: since calculating the difference in heading takes longer time than checking pairwise distance, you should check the distance first, and only compare the heading if the creatures are close to each other. 

If you want to get even more efficient, you could save half the pairwise distance checks by not comparing B to A if you have already compared A to B. To do this, you could sort the creatures by some ID once, and in your iteration you only compare distances if the first creature has lower ID than the second. However, this will most likely not impact you runtime significantly. 

EDIT: I tried implementing a grid structure, but since the creatures are spaced on a 500x500 area, and their view distance is 100, the maximum speedup is only about \$\frac{25}{9}\$. However, I managed to get everything running about 3 times faster by switching to checking distance first, checking distance squared instead of distance, and using a grid. It's not very pretty, but it's something that can be improved:

import math
import random
import time

def getAngle(c1, c2):
    dx=c2.x-c1.x
    dy=c2.y-c1.y
    rads=math.atan2(dy,dx)
    return rads

def getDist(c1, c2):
    return (c1.x-c2.x)**2 + (c1.y-c2.y)**2

def angleDiff(source,target):
    a = target - source
    a = (a + math.pi) % (2*math.pi) - math.pi
    return a

class Creature(object):
    """A virtual creature"""
    def __init__(self):
        self.x = 500*random.random()
        self.y = 500*random.random()
        self.heading=random.random()*2*math.pi
        self.vision_right = False
        self.vision_left = False
        self.FOV = 60/180*math.pi
        self.viewDistanceSq = 100**2

def check_visibility(creature, other_creature):
    if getDist(creature, other_creature) &lt; creature.viewDistanceSq:
        ang = angleDiff(creature.heading,getAngle(creature,other_creature))
        if abs(ang) &lt; creature.FOV:
            if ang &lt; 0:
                creature.vision_left = True #vision_left side
                if creature.vision_right:
                    return True
            else:
                creature.vision_right = True #vision_right side
                if creature.vision_left:
                    return True
    return False

def check_neighbors(creature, grid, i, j):
    for di in range(-1, 2):
        if not 0 &lt;= i+di &lt; 5:
            continue
        for dj in range(-1, 2):
            if not 0 &lt;= j+dj &lt; 5:
                continue
            for other_creature in grid[i+di][j+dj]:
                if creature == other_creature:
                    continue
                checked = check_visibility(creature, other_creature)
                if checked:
                    return

def run_simulation(creatures, grid):
    for creature in creatures:
        grid[int(creature.x/100)][int(creature.y/100)].append(creature)

    for i, row in enumerate(grid):
        for j, cell in enumerate(row):
            for creature in cell:
                check_neighbors(creature, grid, i, j)

creatures=[Creature() for _ in range(2000)]
t0 = time.clock()
for _ in range(1):
    grid = [[[] for i in range(5)] for j in range(6)]
    run_simulation(creatures, grid)
t1 = time.clock()
print(t1-t0)