As soon as I'm able, I usually start with Andariel in Nightmare. She doesn't drop the best equipment, but sometimes you might get lucky with a decent unique or set item. Andariel is also a prime source for the Stone of Jordan; she can only drop three of the unique rings in the game, and the Stone of Jordan happens to be one of them (Manald Heal and Nagelring are the other two - and the bane of my existence, it seems).
Mephisto is great to run in Nightmare. He drops a lot of decent equipment, and while most of it might not be end-game stuff, it's usually enough to get you through parts of Hell (by either using it yourself or trading to other players).
Just for kicks, I also go to Shenk, Eldritch, and Pindleskin in Nightmare, just to help supplement my Magic Find runs. I generally don't find anything amazing, but there's always a chance that something good might pop up.
Also, don't underestimate Cows, even in Normal or Nightmare. They are the source of many good socketable items, as well as gems to trade to crafters for equipment or runes.
We gotta make a change...
It's time for us as a people to start makin' some changes.
Let's change the way we eat, let's change the way we live
and let's change the way we treat each other.
You see the old way wasn't working so it's on us to do
what we gotta do, to survive. Tupac Shakur
100% Legit baal runners SICK_Bambi 93 Barb (46th barb)
SICK_Paladin 95 Necromancer (12th necro)
SICK_ferret 95 Assassin (10th sin) ~~us West Ladder~~
Gems really aren't worth much on their own, but you'll probably be able to get some decent equipment or mid-level runes by trading them in bulk.
When I'm first getting started, I usually pick up every gem I find (whether it be chipped, flawed, or flawless), and place them on a mule that has been given the Horadric Cube. The gems are transmuted until I start getting a decent collection of perfect gems, which are then tranferred to a dedicated mule (I like to be organized). I keep doing this until I have approximately 20-40 perfect gems, and then I'll trade those gems for a Pul, Lem, or Um rune (this varies according to your realm and what prices are now that the Ladder season's new). Rinse and repeat.
Eventually you can stop picking up every single gem and just focus on the flawless ones. By that time, you'll probably have your Magic Find character fully equipped so you can focus on outfitting another character.