I don't understand how/why Grado has been "definitely ruled out" and how you can even form an opinion to "dislike them" - have you ever heard or used one? I'm not trying to start a lot of drama, I just fear you're not giving them a fair shake.
Regarding what headphones you should consider, I have three different opinions based on reading your introductory post, and you'll have to decide which one you like (and I really have no emotional investment in any of them over another - get what you want, because as the saying goes, if you don't love it in the store, you won't wear it on the street).
Firstly, the AKG K701 are worth mentioning here - they'll do a respectable job with the music you've outlined, as well as music you haven't (they're competent all-around headphones). They're also fairly comfortable (some people complain about the bumps on the headband, which wasn't a complaint for me, but it's out there - iirc the K702 lacks the bumps). I like these as a suggestion also because you mentioned them being available locally - I'm of the mind that you might want to try them first (more or less no matter what), simply because then you'll know if they're for you, and they're one of the few options that can be returned if you're unsatisfied. Sound-wise, they're fairly leveled out, lean a little bit towards bright, and have a very wide/large soundstage (somewhat unnatural compared to a lot of other headphones, but it doesn't make music sound unnatural).
Secondly, Sennheiser does deserve a mention. My criticisms are related to price/performance (due to their recent MAP-enforcement), and voicing. Regarding voicing, I think the "veil" is a little bit over-blown as a phenomenon (I haven't heard the 650; I owned the 580 for a number of years, and tried them with the grilles off (which is fairly similar to the 600), the 650 are supposed to be darker still though) - but you should still recognize that they're relatively laid-back headphones with a treble roll-off (it isn't dramatic, but it's there). I think they'd be fine with the music you want to listen to, but they aren't a "toe tapping" headphone IMHO; they do a fine job, and I agree with the general thrust that they're a good candidate as a "first time" purchase because of how generally liveable they are (I don't think anyone could really hate them, they sound good, fit well enough, etc). I'd agree with disastermouse's comments about the bass not being like an over-done car system, and the "faults" not being a huge issue for someone with limited experience (I'd add that basically any good, top-tier headphone would fit into that). My big gripe is the price - the HD 600 run $399 thanks to the MAP, and I don't think they're "twice as good" as the SR-225 or K701 (which are both around $200-$250); I think this fits into the "spend double for 3%" thing fairly well, unfortunately. And based on that, it's a tougher suggestion. That said, you won't get their sound anywhere else - so they do certainly provide something unique.
Thirdly, Grado (specifically the SR-225). I think they will hit your "get into the music" better than the AKGs or Sennheisers, and they're quite comfortable (imho). They're also very easily driven. Sound-wise, they'll be brighter than the AKGs, but it isn't clash-and-trash like a lot of stereotypically bright headphones (I would posit this is a function of their relatively warm and clear tonal balance). Given the kinds of music you listed, I can't think of a better suggestion as far as sound or features. They're also (likely) the least expensive option, and I think they'd be a very good fit for you. The primary concern I'd have related to a Prestige series headphone (the "SR" headphones), would be the relatively small/narrow soundstage - it isn't dysfunctional, but it isn't going to show up the AKG or Sennheiser. Basically if gaming or movies are a concern, I'd look at the AKG or Sennheiser perhaps a bit more seriously.
I think any of these three would be a good choice, and that you'd probably enjoy any of them - the AKG and Sennheiser should have some consideration given to amplification (the AKG because they're relatively insensitive, and the Sennheiser because they're relatively high impedance + reactive), but honestly all three are suitable candidates. The Grado should be the least expensive, but don't have the best soundstage on the block, the Sennheiser are expensive for what they are, and the AKG are a good "middle of the road" choice (and also, based on the OP, returnable as well). I can answer more specific questions about the above comments if that helps too.
Regarding the Bose suggestion, I like the QC15 quite a lot as a closed headphone, but I don't think they'd be my first choice for rock'n'roll. They're very comfortable and fairly well balanced as headphones go, but not without their own quirks. The AE2 will be substantially more forgiving (if you listen to a lot of "bad" stuff, the AE2 will do better than any of the above, including the QC15), and a fairly warm and relaxed headphone, the fault with the AE2 is that they're substantially more forgiving as well.
They're less money than the rest, but I'm not sure they're a good suggestion unless you need a very forgiving and easy-going headphone - generally I'm more apt to suggest the AE2 for multimedia content versus pure music listening.
Besides, I can't imagine them being confortable at all (although I obviously have never worn them, so I can't say)
