Fooled by Randomness was written first. I found it quite insightful. Having read it, the Black Swan felt like a rehash of the same ideas, while the narrator (Taleb) comes across as particularly insufferable.

If you've read the Black Swan already that's fine. My recommendation is mostly addressed to those who have read neither.