With Blackalicious and Jurassic 5, if for know other reason than they feature my two favourite rappers, Gift of Gab and Chali 2na. If you're looking for so-called lyrical dexterity and skillz etc, these fellows are the dons, and neither (thankfully) are what you'd call 'gangsta'. For something a little more underground, try MF Doom.

As far as particular albums by these go, I'd pick Nia by Blackalicious, Quality Control from J5 and last year's Dangerdoom collaboration between MF Doom and DJ Dangermouse.

I realised that I enjoyed certain rap tracks and heard parts of Eminem's Marshall Mathers album in a record shop once and bought that and then the follow ups. If you like lyrical content (and not easily offended) then you should enjoy this - he is funny, brave, direct and rude. It also has rich layers of melody and fantastic rhythm tracks.

Public Enemy-wise, I would recommend 'Muse Sick-N-Hour Mess Age'. By far their most accessible album and - due to using a live drummer - by far the most toe tappy.

The other theoretically more important early stuff can be a bit cold, annoying and quite horribly dated in my opinion.

...I would recommend OutKast, particularly Speakerboxxx/The Love Below. Although arguably half of it (The Love Below) isn't rap, the Speakerboxxx half stands alone as a great rap album.

Also, I've never investigated much beyond the singles, but I think Dizzee Rascal's pretty good too. I'd give him some kudos just for the line, "I'm old school like Happy Shopper" actually.

...just go and buy some sort of historical Best Of. There are thousands of absoloutely brilliant hip hop tracks and almost no brilliant hip hop albums. And hurry before you get to the age when you look comical singing along to it.

For story telling...

The Coup - Me and jesus the Pimp in a '79
Boogie Down Productions - Loves gonna getcha (material love)
Snoop Dogg - Imagine

Laid back....

Dr Dre - Still Dre
D'Angelo - Devil's Pie
B2K - Bump Bump Bump

Energy...

NWA - Straight Outta Compton
Ice T - The Hunted Child

Great hooks...

Scarface - My block
Brand Nubian - All for one
j.V.C. Force - Strong island

Pure good times...

Young MC - Bust a Move
Skee-lo - I wish
Busta Rhymes - Woo hah! - Got you all in check

Dark...

DMX - Damien
Basehead - Ode to my favourite beer
Root Manuva - The Falling

UK...

N-Dubz - Better not waste my time
Akala - Bullshit

Holy Trinity....

Tupac - Changes
Nas - Let there be light
Jay-Z - H to the Izzo

Old School....

Grandmaster Flash and the Furious Five - The Message
Afrika Bambaataa - What's the name of this nation?

Ladies -

Anquette - Janet Reno
The lady of rage - Afro Puffs
Eve - Who's that Girl

Challenge...

Tim Dog - Fuck Compton

Tongue twisters....

Bus driver - Imaginary Places

Political....

Maroons - If
Dead Prez - Know your enemy

that should get you started...

If you can get hold of "Hip Hop Don't Stop - The Greatest", mixed by DJ Prime Cuts, that's arguably the best overview of (mostly old school) hip-hop around.
If not, here's my selection, in no special order. If you don't like any of these, forget about rap; life's too short.

KNOW HOW - Young MC (best party hip hop track of all?)
EYE KNOW and THE MAGIC NUMBER - De La Soul (great hippy rap)
THE MESSAGE - Grandmaster Flash (you know this already, surely)
I KNOW YOU GOT SOUL - Eric B and Rakim (cool and relaxed)
AFTER HOURS - A Tribe Called Quest (cool and relaxed)
SONS OF 3RD BASS - 3rd Bass (a bit shouty but with humour)
MAMA'S ALWAYS ON STAGE - Arrested Development (hippy rap)
TELEVISION, THE DRUG OF THE NATION - Disposable Heroes of Hiphoprisy (as close to Gil Scott-Heron as you'll find)
JURASS FINISH FIRST - Jurassic 5 (coolest drum beat of all time?)
GRAVEL PIT and JAH WORLD - Wu Tang Clan (great act, not shouty on these)
A HAUNTING - Roots Manuva (British rapper, smart and knowing)
WASH IT DOWN - K'Naan (Somali ex-soldier who's unimpressed by gangstas)
BY THE TIME I GET TO PHOENIX - Public Enemy (angry and shouty, but righteously so and an awesome beast)
GIVE IT UP - Public Enemy (PE at their most listenable)

Dedicated rap fans might cringe at some of these, but I like 'em.
Although it's true that great hip hop albums are rarer than hen's teeth, these are two genuine classics:
"It Takes A Nation Of Millions To Hold Us Back" by Public Enemy (shouty) and "3 Feet High & Rising" by De La Soul (anti-shouty).

If in your quest for rap treasure you chance upon the single version of "Love Sick" by Gang Starr, let me know will you?

Got to say that if you took the current best-selling hip hop artists as your starting point, you would do the genre as a whole a disservice.
Check out, in no particular order:
Black star (or any of Talib Kweli and Mos Def's solo "joints")

Tribe called Quest (espacially "Low end Theory" and "Midnight Marauders")

In fact the whole Native Tongue "clique"; Tribe, De La Soul (whose later albums have got better inversely proportionately to the amount of attention they get) Black Sheep, Brand Nubian and the Jungle Brothers.
Gang Starr's "Step in the arena"

Lupe Fiasco's "Food and Liquor"

Missy Elliot's "Under Construction" and "Supa Dupa Fly"

The Pharcyde's "Bizzare ride to the..."

you might take to it, you might not. I tried!

Come on you guys, you forgot the master.
He cooks MC's like a pound of bacon.
Van.
Vanilla.
Ice.
He da man.

...but can I also suggest that when you feel up to it you should explore the work of Biggie Smalls, a/k/a Notorious B.I.G. (recommend the Ready To Die album) and the lesser known, equally cruelly short lived and slightly more gothic Big Punisher (Capital Punishment), two of the most joyfully rude and at the same time fantastically inventive word manglers ever to crush a mic (psych!)

All together now;

'Meanwhile in the middle of Little Italy,
Little did we know that we riddled two middle men
Who didn't do diddly.'

Big Pun 'Twinz'

3 Feet Deep

Vicious Battle Raps

We Know Something

Great tunes AND great vids - DJ Format's "Music For The Mature B-Boy" and "If You Can't Join 'Em, Beat 'Em" are must have items for lovers of the more old school end of the market. And yes, that is indeed Chali 2na and Akil of Jurassic 5 fame on the third track. Word.

I also suggest Cypress Hill's "Black Sunday" - the 90s stoner's choice.

Ice Cube - It was a good Day
Jurassic 5 - Concrete Schoolyard
Dilated Peoples - Worst Comes to Worst
Roots Manuva - Witness (1 Hope)

Jay-Z - try some stuff from the Blueprint album

Kanye West - avoid the ego, his 1st 2 albums are great
Mos Def

...in that Rap/HipHop is (generally) a very much a track-centric rather than album based, er, thang.

I recently did a mate a favour by converting his entire cache of hip hop vinyl into mp3 and thence onto cd for him. For every "O.P.P." (Naughty by Nature) and similar standouts, it's outnumbered 6 to 1 or more by underwhelming, phonus-balonus, watery thin gruel.

Perhaps it's my tastes that lead me to get out my micrometer and sharpest scalpel to carve off some nano shrift when it's not the absolute top of the hip-hop shop, and I'm naturally inclined to give far more latitude to rock & pop meanderings, but there you go.

The drip-da-dip word smithery of raps dawning appeals to me alot more than the spurious vanity of today's incarnation. I believe Grime is the genuine article and should be recognised as a successor to the word-roll throne.

Here's your education:
Kano - London Town (avoid any R & B tracks)
Dizzee Rascal - I Luv U
Wiley - 50/50
Grapple Grippin - Stuck To You/Stuck To My Shoe
SOS Hackney - Hackney Shrouded
Lady Sovereign - Hoodie

Surely a white, middle class Saf'end lad can get away with refering to the sound of East London?

but as live in an East London borough, work in another, and didn't refer to the Sound of East London, I personally will be giving any usage both the the skunk eye and shrift on a pico-, nay, nano-scale.

Well, I often drift to the East London boroughs.
So I'm letting myself off on this one.

and to be fair, I don't substain a middle class mentality. Neither do I try and merge with the working classes.

I keep the middle ground.

but I would highly recommend an album I got last year by Surreal and the Sound Providers called True Indeed. Not shouty by any means, very nice grooves.

Voodoo by D'Angelo is mostly chilled out with some Prince-like grooves if you're into that sort of thing. Could have done with lossing a couple of tracks though.

Of any dabbling I've done in this area these are the standouts so far. I keep meaning to check out A Tribe Called Quest though - anything I've heard of their's I have liked.