I just finished it, and it was good. Very Beneath a Steel Sky-esque, with a hint of Full Throttle (I'm not even sure why, but some parts of GR reminded me of some parts of FT). I really liked Gemini Rue.
It is not exempt from a few shortcomings: the controls and interface kinda suck, combat is God awful (not even sure why they felt the need to include combat at all: it really feels out of place), everyone relevant lives in the same one condo, there are not that many locations in the game.
But the good stuff vastly surpasses those. The atmosphere is just great, the visual design is excellent (hand-drawn, visible sketch lines, watercolour-y backdrops, big pixels for character sprints), the story flows well and the dialogue is quite well-written. I concur with
bledcarrot , the pseudo-philosophical, pseudo-inception content that comes across towards the end is a bit meh (or maybe I'm just too grown-up to be affected by it), but it really doesn't work that poorly, mostly because it doesn't "try too hard", which is a common mistake that many plots do. The plot "twist" is introduced/hinted decently, and the "converging stories" device is also used fairly well. The music and voice acting also are top notch.
Overall, Gemini Rue feels old school as fuck, in every respect: it is a greatly atmospheric and utterly enjoyable game that would have worked perfectly in 1994 as it does now.
PS - anyone can recommend similar games, present or past?