Adventure Generation/Background Generation

I recently had a "conference" of sorts with some of my players.  They
felt that we needed to change the nature of the game.  For one thing, they
pointed out that some of my adventures were "too narrow"--there was only
one solution and they had to follow a precise course of events to get
things done, or fail utterly.  While I don't think the problem is as
severe as some of them felt, I do think they may have pointed out a problem
with my approach to GMing and I decided to look into other options.

(Other problems are less serious.  They want to have more alien characters.
I am willing to do this; it is just that there are less complications when
all or most of the characters are human.)

Now, one of my first thoughts after this conference was along the lines of
"So!  The little darlings want more open-ended adventures, eh?" combined
with a laugh that would make the Joker wet his pants.  (I already have
some truly funny and disturbed ideas...like an assassination attempt that
will involve singing Chip 'n Dale robots who explode after they do their
"I'm Chip...I'm Dale..." routine.)  More important, though, is that the
problem seems to have stemmed from overplanning.  At the same time, I do
not want to simply leave everything open to chance because I have a feeling
that the adventures will simply fall apart if I do.  Does anyone have
suggestions, advice, interesting stories, etc. about how to set up an
adventure with a general scenario, with enough detail that it will be
fun and original, but not so much details that your players are locked into
a single path that they must figure out and follow?  What do people plan
and write down in advance...what do they leave to chance...and so on.

Thanks in advance.