The earliest death I can clearly recall was in my very first world back in August, 2010.
I found a crater, or an entrance to a cave with a dungeon plopped right in the middle. Being very new to combat, I thought my wooden sword coupled with circle-strafing would be enough. Nope. Within seconds I was surrounded then promptly mauled.
That tainted my perception of dungeons even to this day. I approach with extreme caution even if fully armed.
(But if you're talking my earliest/first death in my last play session, it was falling off a sand pillar.)