a few suggestions,

No one lives forever (not much story but many awesome characters),
Deus ex,
Planescape torment,
if you have a gamecube, eternal darkness (awesome story and INSANE production values)