I've been collecting these from Notch's blog comments for about 2 months. Here goes:
-Underground lakes, Underground rivers. ACTUAL rivers, not spring tiles - meaning they'd be much longer and not depend on having any vertical drop.
-Volcanoes & volcanic eruptions (rare). Lava should cool if outside a cave for too long.
-Geysers and hot springs (which heal you). Found only if a pool of water is very near lava at high elevations.
-Stalagtites and Stalagmites in caves. Give caves the splendor they have in real life!
-Dynamic Trees! Different size (height + width) trees based on age and SPECIES of tree. Numerous tree species.
-Some rare trees grow to enormous size (think Redwoods). Palm trees & Jungles.
-Vines that grow up buildings and cliffs!
-Climate zones: separate heightmaps (desert is more flat than mountains) and changed tiletypes + large boulders, old trees, ancient random ruins, hostile villages
-Weather & Seasons (-ICE! In winter, water will freeze! Even waterfalls may freeze!)
-Snow / ice / WIND on mountain-tops [also, BIGGER mountains please!]
-Bake dirt in a furnace to get bricks.
-Iron Fire baskets: Big torches that take up a whole block
-Coral reefs, Sea life, Sea monsters, Sunken ships (with treasure!)!
-Clams which you can make clam soup with, seaweed and various plants could grow on the bottom with fishes and squids swimming around which you could kill with a spear or catch with a fishing rod, and sea monsters in deep and darker waters
-2D sprites grow on grass blocks to break up the terrain and give it more life
-more metals (copper, silver, steel?) & more gems (saphire / ruby / emerald / jade)
-gold coins, gold bars, gold-torches, gold-adorned iron/diamond armor (iron chestplate recipe, fill space with gold)
-gold goblets, crowns, other treasures (
http://bit.ly/deQPeI)
-Boats & Cannons, Teleporters, Elevators, Compass, Catapult, Swimming fins, Fishing pole, backpack
-Carryable torches, light path as you walk, along with reverting back to darker nights
-Hammer & anvil, used to repair weapons and armor. Need iron hammer to repair iron armor. Diamond for diamond.
-Flying machines: Hot-air balloons, blimps, AIRSHIPS!!!
-Placable waypoints & player location on map!
-Beds. When used, health gradually restores. In single-player, time speeds up.
-Blanket: Faster bed healing. Cloth color determines blanket color.
-Birds, deer, moose, bears, panthers/tigers, wolves (howl at the moon), rabbits, other fluff wildlife