I don't think it should be too labyrinthine. Grunty's Industries was a pain in the neck, it was practially Mumbo's Mountain x3 or 4 in terms of size, and that got pretty annoying.
With the expanding world mechanic, I think that having something the size of Witchyworld could be pretty fun. Yeah, sure, it's big, but as you become familiar with the main area, and are able to expand that world by about 25%, it becomes a bit easier to digest as you are taking on the world bit by bit, already knowing part of the layout.
Honestly, as long as they don't make it too empty, or have insane amount of collectables, then I'm OK with that. I think Tooie got it about 60-70% right in terms of level size. It went slightly overboard with backtracking.
I just don't want Project Ukelele to be a game I pick up on the day of launch, play it for about 3-4 hours, and then enter the final boss/level. I want it to take time, to feel like I've got a sufficient game worth the money I spent, but not so much time like DK64. So somewhere around the 30-50 hour mark in terms of first-time playing would be grand in my opinion