so you guys would suggest me to play Psychonauts after finishing with BG&E? I am almost ready to buy... I am waiting for a miracle maybe for the game to appear in GOG's catalog (highly unlikely to happen as i suspect)....

Well I'd only recently decided that psychonauts was on my xbox originals shopping list but then my TV died so I can't get it on 360. Good opportunity for GOG...

You can play it free on gametap.
That's how I played through it.

Am I the only one who thinks that the gameplay in Starfox Adventures on Gamecube is really similar to BGE? The combat is almost identical (one button to swing a staff with emphasis on combos and dodging). You had a partner, who helped you get through barriers and a frst person shooty weapon. The emphasis was on linear story prgression rather than collecting certain special items. The Fuel cells looked and functioned similarly to the pearls and the penultimate battle in BGE felt a lot like a Starfox battle. Obviously the themes and settings are different, but I think it's a lot more like SFA than any Zelda game (although SFA was heavily influenced by Zelda anyway).
SFA recieved a lot of criticism in its day for not being a "proper" Starfox title, but it was a solid adventure game and Rare's last great game for a Nintendo system. I don't think it's as good as BGE, there's not much atmosphere or emotion, but it's suprising to see so many shared concepts...

Prince of Persia: The Sands of Time. And maybe the two sequels.

I'd like to jump on the Psychonauts Bandwagon, it's not the same gameplay, but the game experience and atmosphere is similar.
I also agree with Kingoftherings, Prince of Persia: The Sands of Time has that same feeling.
I disagree with Yogibeer though.
Fable? A good game, but the atmosphere is totaly different.

What about stealth? I know there was a very little of that in Wind Waker (like, half of one dungeon). What about the other titles that have been mentioned?

BG&E has a very "Studio Ghibli"-like atmosphere (that studio makes animated movies). So have "Ico", "Shadow of the Colossus" and the forthcoming "Last Guardian". I can't describe it any better now, but to me there is a connection (although I don't own those Sony titles myself).

Nobody mentioned Little Big Adventure? It's less arcadish and has no team dynamics, but the vibe from the world and gameplay diversity are very similar.
Both have pretty advanced technology, weird creatures, environment manipulation, world exploration, some acrobatics and fighting, vehicles, as well as dialogs and inventory. Both have great graphics (if you account for the release date of LBA).
A pity it's not on gog, BTW. It was a true game design breakthrough.

Psychonauts. But I would recommend even more Little Big Adventure 1 and Little Big Adventure 2. LBA 1 has VERY clumsy controls, though. LBA 2 is marvellous.

Don't. Fable is more a "traditionnal" RPG with some stuff added like you getting fatter is you eat too much or the possibility to marry. Not the same type of game at all.

Oh dear god no. Ubisoft will screw it up with it's "Casual game" bullshit shift.
I suggest you to get Rayman and Prince of Persia Sands of Time/Warrior Within. Both are made by the same people who made Beyond Good and Evil. If you are up for stealth, Metal Gear Solid 1-3 and Splinter Cell Chaos Theory are also worth to note. For more plattformer get a Snes and play Donkey Kong County 2 and Terranigma.
Oh, and Psychonauts 83

Maybe Soul Reaver games. But if you play one of Legacy of Kain games, you'll have to play them all. It's quite a journey. Tip: Skip Blood Omen 2, it's awful and unnecessary. Not stealth in those games, though.

Lol, I agree. Both games are mediocre and way waaaay overhyped.

id suggest scrapland, but make sure to crack it, has starfuck on it.

its a good game with both ship based and meele based combat,