i would actually divide his discography into three: the Asylum period, the Island trilogy, and the post-Island period.
his first two albums, Closing Time and Heart of Saturday Night, while rooted in jazzy blues, have a bit of a country/folk twang to them.
the twang is dropped completely by his third album, Nighthawks at the Diner, which is a love it or hate it album (i love it). he turned the studio into a nightclub and invited a bunch of friends and acquaintances to a live performance. that performance became Nighthawks, and it's pretty much the fruition of Waits' "beatnik" persona, which he pretty much maintained for all the rest of his albums on Asylum Records.
his last album for Asylum was Heartattack and Vine, and you can hear the beginning of his transition to the more esoteric sound that defined his first three albums for Island Records (which i consider his masterpieces): Swordfishtrombones, Rain Dogs and Frank's Wild Years.
after the live album, Big Time, waits took a hiatus for a few years and came back with Bone Machine, which took him into slightly more cacophonous and experimental territory, but still founded on the sound he developed with his Island Trilogy.
The Black Rider was his last album for Island, written with William Burroughs as the book for a play of the same name. i like this album more than most people do. since then, he's been on Anti (Epitaph) Records, with consistently solid stuff, but no real new ground broken.
so, here are my recommendations:
for the Asylum era, start with Closing Time (so you can hear how he started his career) and Small Change (IMHO, the best of his early albums).
for the Island era, the holy trinity is unbeatable: Swordfishtrombones, Rain Dogs and Frank's Wild Years. most people will probably say Rain Dogs is the best, i'll only say it's the easiest to begin with.
for everything else, it's pretty much a matter of taste, but Alice and Blood Money (released at the same time) are both quite good.
hope that helps!