I love both games and honestly I don't really see the connection, either. I guess I'm overlooking something really obvious that links the two.
In one word, gameplay. In more words, character creation and development, similar skill systems with meaningful choices, well defined but different paths through the game depending on those choices, wrapped in an FPS package with a good and interesting story.
That about sums it up I think. Totally different settings and stories, yes, but the gameplay mechanics were very similar. And simple as it may sound, I don't know of any other games like those two, with the exception of System Shock 2, which came before (and perhaps 1, which I never played).
Until late in Deus Ex resp. VtM:Bloodlines, skill points were very scarce and mattered a lot throughout the story and they
defined how you'd play the games. Deus Ex even had you make exclusive choices for character development with augmentations, which mattered also. In both games, each problem could be solved in at least 3 very different ways, which can be loosely described as sneaking, talking or fighting. (I don't really remember talking in Deus Ex, but it probably had something else instead.)
Note that there weren't
too many skills / paths / choices either. If there were too many, they wouldn't really have made a difference. The amount was just right to be meaningful.