Hmmm… Your right, you don’t want to make the game to linear. You could do something like this;
Each level contains levers, knobs, things to collect and you can reach different places by doing these in a certain pattern or order, so one level could take you to a number of different levels depending on how you solve the puzzle for this level. This would create a sort of maze through the levels as you try to find the prize at the end (ultimate lucidity, points, pie? Something…).
To make variety between the levels you could add different possibilities of lucid dreaming to each level; in one you can fly, in the other you can transform (different forms allow you to go through different doors or locks?) or change time and do magic. Messing with gravity, time or simply the controls is in general a nice trick to keep a game interesting.
Again these are just some ideas… you decide if they are good…