In addition to the names already mentioned:
Hélio Delmiro: in a certain way, one of the fathers of brazilian electric guitar. He was the sideman for Elis Regina's band for a long time.
Has a duo album with pianist César Camargo Mariano that is a classic in brazilian music.
Recommended works:
Elis Regina - Elis at the 13th Montreux Jazz Festival (1982)
Helio Delmiro and Cesar Camargo Mariano - Samambaia (1981)
Helio Delmiro - Compassos (2004)
Heraldo do Monte: for a long time played in Hermeto's group. Has a great 'raw' energy in his playing.. specially in northeastern's rhythms like baião.
Quarteto Novo - Quarteto Novo (1966)
Heraldo do Monte - Heraldo do Monte (1980)
Lula Galvão: great bossa player. Works with Edu Lobo, Rosa Passos, Guinga and others.
Lula Galvao - Bossa da Minha Terra (2009)
Arismar do Espirito Santo: multi-instrumentalist, gained prominence playing electric bass, but is equally great playing the piano, guitar, drums and acoustic/electric bass. One of the finest composers of brazilian jazz/brazilian instrumental music, true genious. His son, Thiago Espirito Santo is also a beast playing the bass.
Arismar do Espirito Santo - Foto do Satélite (2006)
Arismar and Toninho Horta - Cape Horn (2009)
Raphael Rabello: faced an early death, but his recorded work is extensive. A virtuoso playing classical guitar in samba/choro. Gifted composer as well. Yamandu Costa plays in a similar style.
Raphael Rabello - Todos os Tons (1992)
Raphael and Amélia Rabello - Todas as canções (2001)
Daniel Santiago: plays in Hamilton de Holanda's quintet, a 'supergroup' of modern brazilian music. His solo work is great.
Hamilton de Holanda - Brasilianos 1 and 2
Daniel Santiago - On The Way
Daniel Santiago - Metropole
For the vocal stuff i'd suggest:
Edu Lobo - Ao Vivo no Mistura Fina (2007)
Paulinho da Viola - Acustico MTV (2007) and Memorias Cantando (1976)
Cartola - Cartola I and II ('74 and '76)
And then of course Tom Jobim, Chico Buarque, Milton Nascimento, Noel Rosa, Guinga, João Bosco.
My first post here, hope its helpful! Those albums should not be hard to find on the internet.
Sorry but I have nothing to say about Salvador, never been there...