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.
