Fallout 3? Great plot? You've GOT to be trolling here.
Fallout 3 has some of the worst writing in videogames EVER, and while the evil side of the plot is decidedly meh, the good side is offensively horrible. It's so badly written you'd have to pay me for me to play Fallout 3 again.
Mass Effect is kinda meh - the main story is like cutting a movie off about the time the going gets good, and the sidequests are Generic Enemies in Generic Locations dropping Generic Loot.
Jade Empire was fun - the story's decent, but the combat is fun too, so overall I liked it.
But frankly, you're missing out on so much if you think BioShock had a good story. Try System Shock (and System Shock 2), Deus Ex, some of the Neverwinter Nights mods (such as Darkness Over Daggerford). Maybe Fallout/Fallout 2, even if the main story is nothing to write home about. Everything well playable if BioShock works.
EDIT: Also, Stalker. Difficulty, immersion, and a decent plot. Not everyone's cup of tea, but it's got an atmosphere that beats BioShock anyday.