I heartily recommend GangStarr and Masta Ace. Gang Starr is without a doubt my favourite hip hop group of all time. Masta Ace is very good, and I have heard was a huge influence on eminem. His sound is good, his lyrics are both insightful and amusing. Heiroglyphics are another excellent group, Del was/is a member of them (there is like 8-12 or something of them, on a rotating basis). Common is good to, but can get to preachy for me.
Yuh! I love me some Del.
I was even thinking of changing my username to Mr. Bob Dobalina . . .
There’s The Streets, but I’m not sure if they count as hip-hop or not. Their music isn’t like any of the more traditional hip-hop I’ve heard.
I’m not sure about sub-genres, but I’ve been impressed with Dälek, Danger Doom, Goretex, Madlib, Madvillain and some classic stuff by France’s smooth-tongued MC Solaar.
Another slight nitpick: Talib Kweli & Hi-Tek together are called Reflection Eternal, the album they made together is called Train of Thought. It is a very good album though. As is Quality by Talib Kweli and his recent Right About Now “mix-tape”.
Pharoahe Monch’s Internal Affairs is a wonderful (if quite rare) album, especially if you’re a fan of the other Rawkus artists like Kweli and Mos Def.
The Roots are a fantastic group. All of their albums are good but I can especially recommend Things Fall Apart
If you haven’t got/heard any yet then I also recommend early Wu-Tang Clan (I like it all, but the early 90s stuff is by far their best). 36 Chambers is essential as are the early solo albums by Method Man (Tical), Raekwon (Only Built 4 Cuban Linx) and Gza (Liquid Swords). The most recent solo album by Masta Killa (No Said Date) is worth a listen as well.
As previously mentionned by others, De La Soul, Gang Starr, Pete Rock & C.L. Smooth are all very good as well.
I haven’t seen Outkast mentionned at all. All of their stuff is good as well, but Aquemini is my favourite. Very laid-back and fun but surprisingly mature and intelligent at times as well.
Also if you’re into any old school stuff by people who don’t take themselves seriously then how about Slick Rick? The Great Adventures of… is a hilarious album from one of the masters of story telling.
Oh, and early Cypress Hill (The self-titled album and Black Sunday) were very good before they started taking themselves too serious.
I mean, I could go on… 
Lately I’ve been a big fan of Busdriver, who I first heard on the Tony Hawk Underground soundtrack. I think that he’s mostly just going for rhythm over content, but the he’s an amazingly talented MC.