Halls of Origination, a 5-man instance located in Uldum, seems larger and scarier than it actually is. However, it's easy to get the hang of things, and you'll spent most of your dungeoneering time on boss encounters. Trash is pretty thin on the ground.
Halls of Origination bosses drop ilevel 333 loot, which puts it around the pre-heroic blue level. You'll want a lot of this stuff before you start queuing for heroics.
Halls of Origination is basically just seven boss encounters. The only advice I can give you is to kill the big guy in any given pull first, and don't be shy about crowd-controlling the others. Additionally, stay well behind the tank in the hallway before you go outside to Earthrager Ptah. The hall has a series of spawning mob packs (akin to the hallway after the second boss in Halls of Lightning) that will charge and stun the closest person. Ideally, you want this to be your tank. Just as ideally, you do not want to unleash hell on these mobs while your tank is sitting there stunned. But that probably won't happen. Do I sound bitter?