That’s an interesting idea. I have no good answer to your question, but something like a dodecahedron comes to mind, as a ‘trade-off’ between a cube and a sphere.
If the edges were all made as small arcs with extra actuators to rotate them either flat along the surface or outwards to form something that can roll. Might need to do the same for diagonals to get it to roll smoothly?
I like the actuated edges idea. I'm imagining it using an edge to hook the top of a step, pull itself half way up with edge actuation, and then building up momentum and slamming a brake to kick itself onto the stair.