I've always thought one thing that could solve Minecraft from a survival nature: a digging mob.
Basically, the idea came to me while planning for a multiplayer fortress. Without anysort of block protection, all anyone has to do is keep digging forward to victory. All gaps can be crossed with dirt, all walls broken down via hands, and all traps can be punched out.
So why not apply that to single player?
There's a pair of things I would change to Minecraft to make it an actually interesting single player game.
1. Creepers will, upon finding themselves in a dead end, blow up. If they know you're there, but they can't get to you because of a wall, they blow up. If there is a gap/moat, then they do not blow up.
2. Gnomes.
Gnomes are 1x2x1 mobs that can do anything the player can do. They will dig, mine, equip items, steal items, eat minerals, open containers and steal shit. If they come across a gap they want to cross, they will use dirt to make a bridge. If they come across a lava flow they need to cross, they will block it off with dirt. If they come across a wall they need to breach, they will dig it out with basic stone tools.
Wherever they dig, they will dig out 2x2 squares. They will build little alcoves underground where they hoard their stuff. So, if you find all your shit's been stolen, you can possibly reclaim your materials.
They can also use your shit to make stuff. Use your wood to make workbenches. Use your iron to upgrade their armor and weapons. Use redstone to make traps. They won't grow stuff, as they can only eat minerals, but they will still horde/burn your veggies.
This does a few things that will make the difficulty similar to a pvp server.
1. It makes chests not perfect protection
2. It makes simple walls inneffective
3. Any farms you have will need protection
4. It will allow for other mobs to gain access to your fort.
5. Provide a persistent, growing if unchecked, threat to the player