Best example is the album by Digable Planets: Blowout Comb. Probably the best hip-hop album off all time in my book. One unfortunate problem though the group members are Black Panthers and thus very militant in their views.
Blackalicious: Nia. This is hip-hop with a melody in much of it not just percussion and beats. Also a good example of positive message in the music. A lot of it is about spirituality and the lyrics are really against the current state of hip-hop. A good sample of this is the song Shallow Days. You can see the lyrics for it here.
http://www.azlyrics.com/lyrics/black...allowdays.html
As far as something more mainstream the Fugees album: The Score from 1996.
Just a few off the top of my head.