I'd just get The Sinatra Christmas Album. I think it was recently re-released as Have a Jolly Christmas with Frank Sinatra or something along those lines.
As far as individual songs:
Frank Sinatra - Adeste Fideles
Sinatra - It Came Upon a Midnight Clear
Elvis - Santa Claus is Back in Town (awesome song)
Elvis - Blue Christmas (68 Comeback Special version is the best)
Sinatra - The First Noel
Dino - Winter Wonderland
Elvis - O Little Town of Bethlehem
Basically, just get the Sinatra album listed above, in addition to Christmas Peace by Elvis and Dean Martin's recently released Christmas album.
Sinatra, Elvis, and Dino. That's all you need. Even if you don't like any of their other songs, you'll like their Christmas stuff because they are, arguably, the three best singers of all time.