First Moments 

The first thing you'll need to do is take in your surroundings. The ideal spawnpoint is somewhere with mountains, lots of trees, water, animals/non-hostile mobs, and a cave nearby. The worst possible outcome of a spawnpoint is the middle of an ocean, or perhaps on a small island with little to no trees.

Next up, wood. It is probably the biggest, most important resorce on the entire game. Without wood, where would you be? Where would you get your first tools or make other useful items? Wood is very very important. Go to the nearest tree and take all the wood. Go to a few trees, take all the wood until you have enough. (Enough is when you craft them into planks, you'll have more than three stacks.)

When you have your wood, make a crafting table and set it down randomly. You'll have to work fast since a minecraft day is aprox. 15 minutes and you still have a lot more to do. Craft some sticks and make the following items-
+ Wood pickaxe
+ Wood axe
+ Wood hoe
+ Wood sword

The other tools and items can be crafted later, but if you want to you can make the Shovel, a door, and other wooden items as you see fit. Use the axe to take down some more trees and remember- Do not craft all the wood into planks! You can smelt the raw wood trunk for an alternative to coal! It will turn out to be very helpful, especially since you aren't properly equipped to fight hostile mobs yet. 

If you see any non-hostile mobs, such as Cows, Pigs, or Sheep, use your fists to kill as many as possible, but remember to leave 2-6 of them so they can breed. (Depending on how many mobs there are in the first place. If there are only two, kill both of them, you can find more later.) 

Shelter

This is where you will have to choose. Luckily, you will have lots of options. (...Probably.) Depending on where you spawned, different options will come up.

Mountain Biome - Your best bet is building a sort of cave structure into the mountain. Try to make it at least 5x5 and make sure you have an entrace with either a door or a single hole block eye-level so you can see outside and when it is day, but nothing can come inside. I would make a passable wall so Skeletons can't shoot you through the hole. 
Example

Desert - These are tricky because sand will fall and even if there are mountains, digging into them will not make a cave. Nor can you dig down and make a hole. The best thing to do (in my opinion) is use materials you have collected such as wood to make a small shelter. Or, just keep running until you get to a new biome. When making a small structure, you will want to use as little wood possible.
Example


Forest - Forest biomes should be the easiest. With all the wood you will have, you could make a treehouse or build where trees are not. This is where you have lots of options. 
Example

Wide, Open Plains - This is also like the forest, only if you are in the wide open plains you might not have a lot of trees, meaning building a house could be hard. If you have enough wood, a normal smallish house should do. If not, there are two options. Make a cave leading into the ground with an underground dirt home underneath, or mine dirt and have a normal house, only with dirt. 
Example


Mushroom Biome -  Probably the most obvious answer would be to make a house in a mushroom. No more questions.
Examples (There are two!)

No Bed / Bed?

Even if you have aquired a bed, don't sleep on your first night. Spend it upgrading your tools and making the raw wood trunk into coal. Make furnaces, mine lots of stone and coal and iron.