I second Terraria on this one: Terraria is awesome.
Also, if you have a PC version of Minecraft(or just wait for the Better Together Update and play it on Switch or XB1), I would highly recommend giving MineZ a try. It's just a server in Minecraft, but it completely changes the game to a post apocalyptic zombie game, that is immensely challenging, and boasts several new mechanics. If you are looking for a "new" Minecraft experience, definitely check MineZ out.