In the Nethack early game, should I first venture through the Gnomish Mines or Sokoban?

Sokoban and the Gnomish Mines present an interesting set of choices. When you think about which one to attempt first, you have to think about the rewards you'll get, and the dangers you'll face. I'll enumerate these in this answer, but let's first directly address the decision.

In a general sense, Sokoban tends to be easier. The darkness, traps, and occasional out-of-depth mumak attacks in the Mines can utterly destroy characters before they even get anything out of the trip. Meanwhile, most of Sokoban's treasures can be gotten with relative ease.

That said, the treasures in the Mines tend to be more valuable, and the zoo in Sokoban can be a pain. I always find it more useful to step into the Gnomish Mines first and see what it's like before making the decision. If they are well-lit and I can see a good haul and the stairs fairly close, then progress is usually safe. Having a strong pet that has been trained on the earlier floors also makes it a lot easier to take down monsters. But if it is dark (especially if I lack a magic whistle), or if I spy a nasty foe, then I'll high-tail it and do Sokoban.

Gnomish Mines

The rewards of the upper levels of the Gnomish Mines are random tools, fair equipment, and access to Mine Town.

Each floor of the mines is guaranteed to have a tool or two, which if you're really lucky can be a magic lamp or tinning kit or skeleton key or bag of holding. The normal tools aren't all that bad, either, as a spare lantern, towel or sack never hurt anyone.

From the dwarves, you have a chance to find things like dwarven mithril coat or dwarven mattocks. Dangerous to try and get if you're low level, but dwarven mithril coat offers very good defense for the early game. If you don't want to anger dwarves (or can't beat them due to the armor), hobbits sometimes carry elven mithril coat which is almost as good.

Finally, there's Mine Town. It has an altar, whose advantages are highlighted in the other answers. There's also shops that can stock even more tools like found strewn about, and Izchak's shop. Never underestimate the usefulness of a functioning lamp. There is a food store, and sometimes the tool shop stocks an ice box chock full of corpses. Don't buy the ice box, but instead just buy corpses - they tend to be cheap and can be sacrificed.

The dangers of the Gnomish Mines are dangerous foes, traps, and darkness.

Dwarves and gnomes are a painful lot and they can come in decent numbers, and also will not hesitate to break through walls to reach you. Some of them also carry wands, which hurt a lot. Fire and cold will end you very easily. More dangerous, though, you tend to run into things like bees or rothes or mumaks... or if you're really unlucky, soldier ants. The open-ness of the mines makes it very dangerous to engage these.

Traps hurt a lot if you aren't prepared. Magic traps can destroy your equipment, but far more often leave you blinded and surrounded by hostiles. Spike pits deal hefty damage, and may be poisoned to cause your death if you aren't Poison Resistant. Consequently, there are no traps in Sokoban other than the pits that you're just plugging up.

Some levels have a chance to be dark, and these represent a very dangerous trek in the mines. Even with a light source, the benefits of being to immediately see the staircases and incoming danger are very high. If you run into the mines and they are dark, it will only be much harder. But if they are lit, and you can spy close stairs, you can possibly avoid many of the dangers and reap your rewards.

Sokoban

The rewards of Sokoban are lots of food items on each floor, two scrolls of earth, a handful of rings and wands, and either a bag of holding or an amulet of reflection, if you make it through to the end. The food items can be varyingly helpful to an adventurer who is running low, and the rings and wands are simply nice to get somewhat safely.

The final prize can actually change your decision. The rooms in which either prize are found are fixed - so if you've played long enough to know which room is which, you might choose to back away instead of dealing with the zoo.

The dangers of Sokoban are the zoo at the top, mimic boulders, luck penalties and creatures getting in the way.

The zoo is filled with monsters, which may be poisonous or acidic or otherwise an extreme pain. If you're really unlucky, there can be winter wolves or other breath weapon users. Telepathy really helps if you have it, but otherwise you might consider just getting the non-final prizes of the place if you think the battle will be too difficult.

Mimics hurt a lot. That's really all there is to it. If you aren't prepared for it, it can end you. Telepathy, once again, helps.

Luck penalties are had when you botch things up, which tends to happen when creatures get in the way. If you lack methods of firing through boulders, or if you have problems with the puzzle, you can suffer quite drastic penalties as a result of workarounds. And if you're super unlucky, it's actually your pet that's on the other side of the boulder (A magic whistle helps here, as well). So I find that if I lack any method of dealing with enemies getting in the way, I'll skip Sokoban until I find at least something.

For dwarves and gnomes, the Mines are relatively safe, and adventuring as far as Minetown is often a good strategy, particularly if you've found a light source or the mines are lit. Fully exploring the upper levels of the Mines is a good way to find lots of useful items, and a magic lamp in Minetown is a fairly common source of an early wish.

For other races, the decision is often more difficult. Fighting the hostile gnomes and dwarves is a good source of XP, daggers, pick-axes, and occasionally mithril armor, although it's also a good way to get killed if you're not careful; a dwarf with a mattock can do a lot of damage fairly quickly.

Mine town has lots of shops and a temple. So if you haven't found an altar in the main dungeon yet and/or there aren't many shops at the early levels of the main dungeon, it might be worthwhile to go to mine town early. Also: the lower your level is when you reach mine town the more points of protection you get for you money. On the other hand the mines can be dangerous (especially if you're keeping your level low for protection), so you should make sure you're ready before entering the mines.

Sokoban has lots of food, so if you're low on food, doing sokoban first helps. And of course it also has the price at the end, both of which are quite useful. Unlike the mines it's also quite safe to do sokoban: The first three levels don't contain a vast amount of monsters. The last one does, but they're all behind the door, so you can use that to fight them one-on-one, which makes them a lot more manageable.

So if you're doing the protection racket or you feel fit enough and are in desperate need of some shopping or an altar, do mine town first. Otherwise I'd recommend doing sokoban first - especially if you're low on food and don't have either of the possible prices yet.