As much as I enjoyed both Pale Fire and Ada, or Ardor: A Family Chronicle, I cannot, in good conscience, let these be the only Nabokov books to be mentioned here. Having read all his nonfiction and his autobiography over the past three years, I must warn against starting with either of these, two of his most difficult, novels.

You see, Nabokov toys with his readers - he leaves puzzles throughout his books; he writes in defiance of literary criticism (part of his impetus in Pale Fire); he foreshadows with a trail of anagrams. To throw someone in media res of two of his most complex tales (perhaps only surpassed by Lolita and The Gift), might give a premature distaste for Nabokov's heady style.

What I would personally recommend for someone new to Nabokov would be any of Despair, The Real Life of Sebastian Knight, or Transparent Things.

If you like Nabokov, you may also want to try:

Rushdie, Salman - The Satanic Verses

Pynchon, Thomas - The Crying of Lot 49