It's not fantasy, but Circle of Blood (Broken Sword: Shadow of the Templars) is a long, challenging classic that is still as gripping and beautiful today as it was when it came out. It's also for the PS1 and, surprisingly, has a superb port out for the Gameboy Advance (sans voice acting and cutscenes).
The CHZO Mythos games (which I reviewed a while back) are more fantasy based, though I would classify them more in the horror category. It doesn't really get under your skin until the third in the series (Trilby's Notes, considered on of the best AGS game ever made), but as a whole, the series offers great visuals, sharp writing (the creator is a well-known Australian columnist and game-reviewer), memorable characters and a gripping plot. It's also scary as hell, but that's just a bonus.
Out of Order is also free, and tells the story of Hurford, a boy who leaves his room to find, instead of his house, a large, faceless, zoo-like, alien community. Very reminiscent of Adam's most famous serires, and a lot of fun.
But really, I think the absolute best choice for you (and easily one of the finest games ever made) is The Longest Journey. You can likely find it for cheap. It's plot, despite its enormous length, is tightly paced and fast-moving and the production values are fairly high with fantastic art and great voice acting. I'm not going to spoil anything, but know that this game is simply a must-play.
____________________________
Director of the Department of Orderly Disruptions