My 1st 1st structure was, like many here, a 4x3 square house made of dirt!
On my 2nd world, my 1st structure was a cobblestone house about 10x10, floating two squares off the ground with a stone stairway leading up to it. That poor stairway took a lot of beatings from creepers.
My current base of operations is surrounded by a lava moat - no more creeper trouble for me!
My first real structure was a huge dirt tower, and i didnt know doors existed so i closed my "Door" with dirt. It ended up turning into a spider network above ground of stone walkways connecting several stone outposts, each with a mine going downward =D It was all pretty ugly though :biggrin.gif:
My very first structure wasn't even a structure made by me. I started playing on a server that all of my friends from school were playing on before I ever did any single player, the friend who ran the server showed me around the server and he built me a simple little dirt house in the side of a mountain and I ended up expanding it from there.