Grimrock, absolutely.
That's tricky. Start at the centre, but make sure you've got a lot of room available in all directions, because the game typically won't start right in the middle. At least as far as Grimrock is concerned, the grid layout is perfectly consistent throughout the whole thing, so once you've got a complete map of one floor, all the other floors can extrapolate from that (by which I mean that if you've got a staircase down on floor 1, square 13-D, the staircase up on floor 2 will be on square 13-D). You shouldn't need more than one sheet of paper per floor for most games.

That being said, I would recommend turning on the automap. I never thought mapping was much fun, but your mileage may vary.

Stonekeep is a great place to start! I'd say Anvil of Dawn, but that isn't here yet. All Might and Magic games are all worthy of your time as well.

true... :o)

but I guess Stonekeep has the most "dungeony" feel about it, when I hear "dungeon" I immediatelly think of Stonekeep, one of the best games of this genre, and with controls, mechanics and graphics fully acceptable even today (unlike Dungeon Master, sorry, but it's true)

M&M and Wizardry have too much happy exteriors for my taste ;)

Start with Legend of Grimrock, the other ones are better and better ;)

GOG should have a dungeon crawler weekend promo featuring all of the badass dungeon crawlers in their arsenal of games.

Yes, Stonekeep!

Dungeon Hack is pretty awesome! Not sure how easy it is to get but you can customize your dungeon if you like.

If you want to draw your own maps, then I would recommend against a lot of the games that people have mentioned here. The vast majority of them have auto-mapping. Legend of Grimrock is the big exception here, you can play without auto-mapping, and draw your own maps.

Also, see if you can track down Eye of the Beholder.
This is probably the best way to get that game (plus 10 other classic D&D games)

*edit* Of course, if you don't mind auto-mapping, then do listen to the rest of the people here ;) Arx Fatalis, Ultima Underworld, World of Xeen, Lands of Lore, they are all great.

Is it impossible to turn off the auto-map for most of these games, then?

Also, I think I'd prefer to map out only tile-based games. So for Arx Fatalis, Ultima Underworld, and any other game similar, I don't mind an auto-map.

As in first-person Dungeon Crawler?

For games already in GOG:
- Arx Fatalis gets my vote.
- Other that: Lands of Lore, Legend of Grimrock.

Games outside GOG:
- Eye of the Beholder series
- Ravenloft series
- Anvil of Dawn

I don't see a persistent automap anywhere in screens for Eye of the Beholder, Stonekeep, and Lands of Lore. Since Eye of the Beholder is legally(??) free as abandonware, I think I'll make that my first one.

a) There is no legal definition of abandonware.
b) Lands of Lore 1 has a persistent automap, assuming you remember to pick up the map at the castle. If you do, you have an automap, if not, no automap, pen and paper will be your friend.

MM2 had automap, MM1 not.

Well, Eye of the Beholder is too old to run on this PC anyhow. So, it's down to Grimrock, Stonekeep, or Lands of Lore. I'm tempted to go with Grimrock because as someone said, things only get better from what I can see. :)