Here's my suggestions:
The Clash - The Clash: Yeah there's a reason so many people are recommending this album: no one can really pin down what punk is but The Clash is definitely it. The only Clash album you'll ever really need, but no music collection is really complete without it. Plus you can wax cool by dropping Joe Strummer references in passing conversation.
The Velvet Underground - White Light/White Heat: The most underappreciated of VU's albums is also, in my opinion, their best work. Its a headtrip, its unexpected, and it throws the rules out the window. This is where the Underground stops being Warhol's creation and set trends that bands 30 years later still can't beat. John Cale's masterpiece, and that Lou Reed guy ain't bad either.
The Who - A Quick One: Who's Next is very good but A Quick One is chaos. Pure, wonderful chaos.
The Stooges - Raw Power: Basically what Punk/Hardcore/Whatever is supposed to sound like. There's the Bowie produced version thats ass, the new Iggy set which is damned good. Little rawer, lots more power.
Greg Oblivian and Knaughty Knights' stuff is good if challenging to listen to. Same goes for Richard Hell and The Voltoids, all harder stuff thats much better than most can hear. You've really gotta love triphammers and regressive (lack of ********) rock and roll to dig hard on it.
Since you like Costello's current music you really need to hear My Aim is True. This opens the door to Rock and Roll with atypical songwriting, which is a whole other list of recomendations:
Try as much of Eric Burdon's stuff as humanly possible (Animals, War, his personal releases) as he's influenced more artists than can be counted, yet sadly hasn't been acknowledged as he should be (right up there with Reed and Iggy and Bowie in my opinion). Its easy to fall hard into this stuff, and once you do a lot of music sounds like a bad imitation.
Arthur Lee's stuff is gold, if you can pick up Love - Da Capo (get the mono version, yes its on digital) and Forever Changes. Can't really go wrong with the band's stuff, and while its very different than the recommendations in the begining of this thread its also very relevant if you really want to learn/hear rock and roll.