Well I think the thing about Minecraft is that there is no one way to enjoy it the most. What makes it so good is that there are a number of approaches to the game all of which feel rewarding. If you're more interested in the lego aspect of the game, creative mode is probably where you need to be at. It can be a lot of fun to do this on a multiplayer server where you can show off the awesome things you built, and I'd invite you to my own but since it's rented and runs on Bukkit it'll be un-operational between now and whenever Bukkit updates itself for 1.3. Regardless, this mode really is your childhood dream of living in a world of legos finally realized... that couldn't have just been my dream, right? If you do find yourself attracted to that sort of gameplay, then finding a project is exactly what you need to do. You can build elaborate palaces, twisted underground research facilities with elaborate experiments, or giant statues of Doctor Manhattan (giant blue wang included) stretching from the lowest point of the map to the highest point (all three of which I have done).
If you like the idea of a survival horror (which isn't really that horrifying until a Creeper gets near the thing made of valuable materials you just spent the last three days building, or you fall into a dark cavern with nothing but the groans of zombies, clicks of skeleton bones, and slowly approaching hiss of explodey death to keep you company) with some really rewarding exploration and the lego aspect still in play except now you have to go out and painstakingly find every single block you want to use, then the survival mode is probably the way to go. You'll sink countless hours into gathering the materials for your house, fort, or perfect recreation of The Hall of Justice... or wherever it is that you go at night to keep the zombies away, and by the time you've actually got a decent stock of resources you'll probably feel like a badass. The survival mode has another benefit as well, which is that unlike in creative (where you can have as much of any item as you'd like, regardless of how rare it is) the survival mode will really make you work for everything. Even the hopelessly common resources like wood, stone, and dirt will require work since when you need them, you tend to need them in large numbers. But it'll get really rewarding once you develop a decent mineshaft and have the good fortune to occasionally stumble upon some diamonds or even just some iron. And if you decide you're in the market for some really specific object like a pumpkin (or if you're not in a desert biome a cactus) and journey far from home to find it, the moment when you do finally come across it will be worthy of the same sort of celebration you'd hold if you just graduated from college or got married.
I haven't tried the adventure mode, but honestly I have a hard time imagining it'll add anything of real merit to the game. For all it's brilliance, the game's combat department is more than a little lacking, and while stumbling across an NPC village or abandoned fortress in the survival mode generally produces the sort of joy which requires that you change pants on account of the mysterious sticky white liquid that suddenly appeared in the pair you had been wearing, if these kinds of events are scripted in Adventure mode (and I don't know if they are, so perhaps I'm speaking out of my ass) I doubt they'll have the same joy inducing effects.