A lot of people really frown on compilations, but since there is such a huge body of this stuff - including lots of albums that have yet to be reissued in full - label samplers are a decent way to at least find out who you want to explore. Dusty Groove has carried collections from the vaults of Odeon, Elenco, Forma, and Philips. The Blue Brazil series, for example, from Odeon, is worth checking out.
That said, one album you HAVE to have is Afro Sambas by Baden Powell and Vinicius. Be sure you get the original version, though, with Quarteto Em Cy on backing vocals. Powell later re-recorded the album and it's nowhere near as good.