Project Eden. A puzzle game set in a mega city, it reminded me of Ico, make of that what you will.
American McGee's Scrapland. So very under-rated. Great setting and atmosphere with pretty different gameplay. It also has the coolest box art of all time and you can get it for cheap.
Clive Barkers Undying. It's very much like Bioshock, if you've played it you'll know what I mean. Even the Irish accent, christ.
Startopia, a space-station sim. I liked it when I was younger, I don't know how well it's stood the test of time. It does have hitchhiker's guide style encyclopedia entries.