Hmmm. Sounds rather like Torchlight 2: deceptively cute and endearing at first, but with big bastard bosses and unpleasant surprises below the surface. Can't say I ever much went for that art style, but if there's something that effectively communicates challenge to me, it's a giant scorpion.
This game turned out to be a big pleasant surprise for me, hope it does well in sales.
It's worth pointing out the first patch added more difficulty options including a much requested easy mode xP
I've seen this and it looks intriguing, but there's also The Curious Expedition as well(unfortunately, I haven't heard much about the TCE yet).