I'm just getting into his music...Which albums should I start with?
The two Town Hall concerts he did with Mabel Mercer. They each do a solo section and then a few songs together at the end of each concert.
The songlists for both evenings include a lot of the songs they're well known for and the kind of obscure novelties and ballads they enjoyed re-discovering.
If you don't know her, it will be a great way to get to know them both at the same time. The two concerts were re-packaged together. 
Mabel Mercer & Bobby Short At Town Hall / Second Town Hall Concert [LIVE]
After that, probably his Cole Porter and Noel Coward albums--they're kind of definitive. (He does a little Porter and some Coward on the Town Hall concerts too.)
Videos