To a certain extent I don't think there is a conclusive answer to this question, but in the second example you give i.e. 'tall, dark and handsome' the word 'dark' seems to be about physical looks alone, literally tall, dark (eyes/hair/skin) and good-looking.
The Oxford English Dictionary suggests that 'dark' when referring to a person can mean skin, hair or eyes, so it could mean any, or all, of those three.
ODO: Dark (Of a person) having dark skin, hair, or eyes
In contrast I think 'dark stranger' not only refers to physical attributes but to a certain air of mysteriousness that this individual projects.
ODO: Dark 4. Hidden from knowledge; mysterious.
The 'dark stranger' is a trope in romantic fiction which I think draws on both meanings of 'dark' someone who is perhaps exotic-looking but also unknown, so in this sense attractive/exciting.
In Scotland, a tall, dark, stranger is a symbol of good luck in the tradition of first-footing.
The idea of the 'tall, dark stranger' mentioned by a psychic is probably this one.
However, in literature a 'dark stranger' can also be negative drawing on yet another meaning of 'dark':
ODO Dark: 3.3 Suggestive of or arising from evil; sinister
Examples in C19th literature of this mysterious/sinister idea include:
Mr Rochester in Jane Eyre, though not traditionally handsome has 'great dark eyes, and very fine eyes too' and 'sable waves of hair', 'dark eyes and swarth skin' but holds a secret.
Heathcliff in Wuthering Heights who is described as a 'dark-skinned gypsy' with 'deep black eyes' and a 'handsome figure' but can also be seen as a sinister character.