I would play Half Life 2 first, although both are good games. They both have their strengths and weaknesses, but I give Half Life 2 the edge.
Bioshock has the better overall story; it touches on themes that go much deeper than the usual “Aliens are taking over the world” scenarios (Halo, Half Life, etc.) that have become cliché in FPS’s. It’s main strength is its atmosphere, the developer did an amazing job of immersing the player in Rapture and connecting the environment to the objectivism theme. However for all the great atmosphere and story, I didn’t find the gameplay as engaging. Although you are given many options in your plasmids, it felt like the plasmids were just a clever way of having a flamethrower, electricity gun, etc. It didn’t feel like the plasmids were used in enough creative ways besides killing enemies.
Although Bioshock has the better overall story, I think Half Life 2 does a better job of conveying story. Although Bioshock takes a page from Valves playbook, since there aren’t many cutscenes, So much of Bioshock’s story (really the backstory) is told through the audio recordings; whereas in HL2 you actually play through the story or meet up with characters that convey the story to you. I really like the way Valve incorporates the story elements into the gameplay such that you never feel taken out of the game to watch a cutscene and they do a great job with the pacing of the story sections. Half Life 2 also incorporates adventure elements into the gameplay to add some variety, one minute it is an FPS the next you are solving a physics puzzle with the gravity gun. Even though Bioshock has the better atmosphere, I think HL2 has better level design IMO.