Look at Terraria

Terraria isn't just a 2d version of minecraft, it's much more than that. In some ways, I could say that Terraria is a metroid-vania with minecraft elements sprinkled here and there, there are similitude between the two games but ultimately, the progression and sense of discovery in terraria make me prefer this over Minecraft. This is not going to be a Terraria versus Minecraft review, but if I find apt comparisons, I will certainly make them.

Humble beginnings

There is a progression in Terraria, goals to work towards
I suspect that most games of Terraria will go like this: Make a small house, mine, dig, explore, find some decent equipment, fight the skeleton boss, explore the dungeon, find a black key, dig more, explore more, find hell, open chests, get better equipment, fight the wall of flesh, break orbs, break altars, get better and better equipment, craft awesome chainsaws, grind in the corruption and the hallow, fight bosses, win the game. This might sound like a bad thing, but it's not. Of course, the actual process of doing these things won't be as straightforward, you'll want to mess around with your world between each of these steps and sometimes some steps will take longer than others.

Friendly NPCs

Randomized loot is a big part of this and it's great that you'll find items that enable new abilities and powers as the game goes on. You get tiers of armors, some with set bonuses, some without, you can have random modifiers on your items to make them better or worse. The loot game is interesting but not core to the Terraria experience, what is core is the metroidvania part of it, the way you do certain actions then come back to do other stuff that you couldn't do before. The world evolves as you beat certain bosses so items that weren't there once will appear. Floating islands will be populated, enemies will become tougher and you'll add powerful ores to the grounds of your world. Always working towards a better upgrade is a good way to keep the player interested.

Discovery

That being said, the frustrating part is the randomness of the requirements for some of the next steps. Ore that appears randomly on the map in tiny chunks makes the player search for a needle in the haystack and if you need one more bit of adamantite but can't find it, you're going to use a map viewer or something to find yourself some of it. Trying to find certain items is also frustrating and again makes an argument for using external programs.

How I would fix it
Add some in-game items that serve as dowsing rods that you can tune to find certain items. Maybe a treasure hunter NPC that tells you where some items are in a vague way? That would help a lot, especially in huge maps because you would know where to go.

The game doesn't know what it's trying to be
Terraria is full of hands-on, stat boosting items, things that make you double-jump, guns that shoot 33% less ammo, spells that launch fireballs and crystal shards, armors, horseshoes with special immunities, etc. etc. You gather materials to create crafting stations to create better items to defeat more enemies. Yet you still can craft bowls, chairs, lamps, decorative items with no purpose other than decorate. I get why Minecraft does it, because you want to build the most gigantic goomba out of dirt you can or a crazy pyramid made of diamonds for no reason, because you can do just that, but terraria is full of goals and places to explore and enemies to defeat, why is the game also trying to be a sandbox where you jump around, trying to make the prettiest decorations ever?

It gets unfriendly at night, even for the NPCs.

To make matters worse, enemies are legion in Terraria, zombies and slimes at first, then werewolves and unicorns and floating balloons that shoot lasers, then invading goblin legions and ghosts and other undesirables. Sometimes they'll sneak in your houses, fall on your head, generally be nuisances. At least there are no monsters such as the creeper from Minecraft, but why so much decorative stuff? The list of items I can craft is pretty long but I'll never want to make some candles or a statue nor will I make gold and silver bricks. The sense of scale is also different in 2d, you can't really run far away and look at your creations in all their glory.

When the fight is on, it's on, you'll get to hell and immediately you're attacked by teleporting fire imps and massive bone serpents and the first boss will kill you instantly if you don't defeat him by sunrise. Status effects are many and the enemies have annoying patterns, warping around, flying, swimming, always homing like a missile on your location. Fall damage can be brutal at first, lava is always deadly and you can drown pretty easily if you're not careful.

I think I'm not well equipped for Hell yet.

How I would fix this
Either split creative mode with adventure mode or make the 'decorative' items crafted using different stations. That way you still allow all that stuff but split it well enough that you won't be hindered by one or the other category. In creative mode there would be no monsters

The biggest problem with Terraria is how closed it is
Minecraft and Terraria are comparable to a point, there are tons of things to do in both of them, exploring dungeons, jungles, oceans, hell and the like, but when you're done with the original content, Minecraft is far from being over, there are tons of mods that add incredible content such as machines, magic and everything in-between. Terraria's modding scene is less impressive and it must be because the game was released without much support a long time ago. Minecraft is still evolving with new things coming out every so often while Terraria is "done". A console version was announced with new content so that might fix some of my issues, but I really wish the game was more open to modding, then I would see the crazy Industrialcrafts and Thaumacraft of this world. The systems and settings behind Terraria are perfect for such mods.

Discovery, again.

Otherwise Terraria is great, there's so much to do, so much to explore and so many enemies to kill, after a while you really feel like you've got somewhere and that's always great to convey through gameplay.

How I would fix this
Well, I would probably make some mods if I could, all of my issues with the game (Including some I haven't touched because they are quite small such as how you travel in the world and things like that) could be fixed by some mod or another.