don't have it, haven't read it, but it's all about critters from the shadow plane.
[url=http://paizo.com/products/btpy87uz?Pathfinder-Chronicles-The-Great-Bey ond-A-Guide-to-the-Multiverse
It's got good info on the elemental planes, as well as the shadow plane, and the negative energy plane.
I've had a huge amount of fun running elemental plane adventure chains in my campaigns.
edited to add: derp. the link for the great beyond book seems to hate me.
Negative Energy Plane would have plenty of undead, wights, wraiths, and specters being the notable rank and file. For a main bad guy, a vampire or lich.
Since the very nature of the plane is the anti thesis to life players will be constantly bombarded by lethal energies. Any local that reduces are blocks the planes energies would be notable as well as any point where it becomes even more deadly.
Not sure if it's the case in pathfinder but in d&d the negative energy plane used to deal permanent negative energy damage to people... all the time. I guess it's the same on the plane of fire. Travel might be hard on the plane of earth... well I hope they know how to survive on those planes?
Actually even the plane of positive energy kills (burst) you in no time. (does too in Pathfinder, just checked)
I don't think any of the elemental planes had a leader. The various genies are usually portrayed as the most organized power group, but the elder elementals are usually portrayed as more powerful.
You could easily make negative energy elemental-like creatures.
The would be other creatures on the planes as well, like efreet on the plane of fire. Look up the city of brass.
Also, just as on our world there are more ans less deadly environments, so on the the elemental planes are there places safe for those from the prime material.
As a suggestion, make the journey from plane to plane interesting. They could navigate an endless fog from water to air, travel by lighting from air to earth, and sail a sea of magma from earth to fire.
Someone already made negative energy elementals. Also, there are core para-elementals from between the planes: lightning (air and fire), magma (fire and earth), mud (earth and water) and ice (water and air). The fire/water and earth/air pairs don't show up much because those are often considered opposites. (You left fire/air off your list BTW.)
Also, CR 11 sounds a bit low for the leader of an entire plane. I thought there was a category above elder, but maybe that was in 3.5.
Edit: Actually, anything short of a deity ruling an entire plane seems off to me. Remember the inner planes are just as big as any of the outer planes or the material plane. You could even reasonably have whole separate worlds within each inner plane. An elemental ruling such an area would work.
Edit again: Also, IIRC, there are para-elemental areas between the inner planes and the positive and negative energy planes, though I can't remember what most of them are. (I think ash was negative/fire, dust was negative/earth, ...)
Prepare for some AD&D goodness:
.
.
.
.
View from the Positive Pole:
.......------------------Air------------------
....../.........................|..........................\
...../..........................|...........................\
..Smoke................Lightning..................Ice
.../............................|.............................\
../.............................|..............................\
Fire---Radiance----Positive-----Steam-----Water
..\.............................|............................../
...\............................|............................./
..Magma.................Minerals..................Ooze
.....\..........................|.........................../
......\.........................|........................../
.......-----------------Earth------------------
View from the Negative Pole:
.......------------------Air------------------
....../.........................|..........................\
...../..........................|...........................\
..Smoke.................Vacuum....................Ice
.../............................|.............................\
../.............................|..............................\
Fire------Ash-----Negative-----Salt------Water
..\.............................|............................../
...\............................|............................./
..Magma...................Dust....................Ooze
.....\..........................|.........................../
......\.........................|........................../
.......-----------------Earth------------------
The inner Ring are the 8 Quasi-Elemental Planes.
Ooze, Magma, Smoke and Ice are the Para-Elemental Planes.
More on that here on Wikipedia.
Could you build that into a 3d model for us real quick? :)
Take a d6 or a d8. On a d6 the elemental and energy planes are the faces (they're on the points on a d8) while the quasi- and para-elemental planes are the edges (still on the edges on a d8).
Before D&D4 came out, there was some discussion of the Points of Light setting. IIRC, the elemental planes were replaced by the elemental chaos, which ended up looking a lot like limbo. Just a suggestion of what the middle of the cube might look like.
Also, if you are using a cube, you can't get directly from Fire to Water, Earth to Air or Positive to Negative. You'd have to go through the center or one of the other faces first.
Edit: Well, since you have more than 3 dimensions to work with, that doesn't necessarily have to be true.
