I can't really help you in regards to Naxx, as I haven't done it myself yet, but I can help you with your other questions.
As far as the Factions you can gain rep for by wearing tabards in heroics, I would shoot for Kirin Tor first, that way you can get your head enchant. That's what I'm doing currently.
I would also look into unlocking the Sons of Hodir faction, which you can do by starting the quest in Storm Peaks in K3: They Took Our Men. It's a pretty long chain, but it's also a lot of fun. The Sons of Hodir faction sells shoulder enchants, so you're going to want to hit exalted with them asap so you can buy the best one.
Another good faction to work on is the Oracles in Scholazar Basin. They have a really nice epic trinket, plus at revered you can buy the egg from them, which has a chance to hatch into a Green Proto-drake mount. You can start working on their faction by killing the cat
Pitch, which leads to a quest chain where you help out the Frenzyheart tribe for a while, and then the Oracles. It ultimately leads to the quest A Hero's Burden, which you will need a group for. In the quest you get to pick between the two different factions.
As far as heroics, it really depends on your gear. Anobix has a link to the Rawr application in his sig, which lets you upload your character, and then it tells you about different items that will be upgrades for you, and where they drop. Nexus is pretty good. I've gotten three blues and a pair of purple gloves from there. You'll probably want to start at the bottom and work your way up though, doing UK, Nexus, AN, and OK first. You don't have to of course, it's just a good idea to get yourself situated and used to the mechanics of heroics.
Hope that helps. :-)
Edited, Apr 12th 2009 3:02pm by PigtailsOfDoom