Except for Wing Commander, I just can't play linear games and enjoy them. To a certain extent you're right, many modern games just don't cut it with creativity and open-endedness, there are some exceptions to this, and there are plenty of old school adventure games that are totally linear - I loved Monkey Island as a kid, but I couldn't touch it now, there's just no variation.
Wing Commander isn't open ended because once you've played the game enough times you'll always end up with the same eventualities. That said, you can go about things differently every time so there is
some replay appeal, well there must be, I'm still playing them every year without fail.
As for good open ended games, first off, Sid Meier's Pirates! - both the 1987 version and the 2004 remake.
@Quarto will vouch for this, the variation of the adventure is unrivaled. It is far less shallow than Privateer, less lonely and much more absorbing. Also, Civilization: not adventure, but you'll never have the same game of Civ twice. Then there's Grand Theft Auto, yes the story is linear, but like Wing Commander the outcomes are different and there's a sense of freedom and immersion you don't get in many other sandbox games, again you can go about missions in any number of ways.
Another one I really like is Commandos, to somebody like me who demands creativity in my gaming experience, this is sweet candy. There's no 'correct' way to win a mission, it's all about improvisation and creativity. The same things never seem to happen twice if you replay a mission. The Hitman series, especially Contracts and Blood Money are two of my all time favourites for the same reason.