So, I've been experimenting with different ways to start the game and play through the game. For a while, for example, I would always do the quests near Terinyo and then dive through the UD and make the trek to the CoC... but as of late I've realized that the CoC is only a 2 day journey from Terinyo, and have tried switching up my playing style. Here's my standard decision making process:

1. Start game, head to Terinyo. Get appropriate quests.
2. Go to Lawintheol, get pickpocket, kill an outlaw. (they're a good first kill, since they can be found on the road right by the Old Barbarian, but are pretty rare in dungeons)
3. Do SMC and get blanket.
4. Kill Kranach. (if he doesn't show up by game day 5 or 6, I often just give up on him)
5. Collect $$ from Sheriff, buy anything useful in Black Market.

6. Does my character have Healing?

Yes: Go to step 7.
No: Do village elder quest, go to step 7.

7. Is the down staircase in the SMC close enough to reach without fighting?

Yes: proceed to step 8.
No: Descend into UD, proceed to step 8.

8. Head due west to CoC. (going straight over the water - it won't kill you)

9. Descend, buy Ratling Food and ditch whatever rations, make a beeline for Dwarf Town.

10. Get first quest (I'm between level 6 and 10 at this point) and Griffyard quest.

11. Head back up (fight in the arena 19 times for money for master thief), go back to Holeinthewall.

12. Join thief guild, get detect traps and stealth, anything else useful.

13. Kill Hotzenplotz (I should have a good wand by this point)

14. Do VD/DD, get bridgebuilding/herbalism, do PC, explore the ID a bit for experience and equipment.

15. Do Griffyard.

16. Descend through UD (if I haven't yet) and max my stats with nearly guaranteed herbs. (use holy water potion I got from Dwarftown to adjust if necessary)

17. Attack the Pyramid!

18. VD with a Pyramid Pickaxe for the wand of teleport. Back to Griffyard with pickaxe (if I didn't have one before) to do some grave digging.

19. Back to Dwarftown to do the rest of the quests, talk to mystic.

At this point, I have to make the decision to start searching for an AoLS or kill Khelly. I usually avoid killing Khelly until I do the High King Cave (my next stop usually), Library, Darkforge, and Gremlin Cave. by this point it's around day 20 and I also have to decide if I want to start the Old Crone quests, or just prepare myself for the ToEF and the big dive.

So, how do you guys usually do it?