I finally made a decision and bought something. I went to BestBuy during my lunch break and used some of Judge_Buff's advice on testing things (thanx alot btw).

I brought my Netbook, iPod Shuffle, Zune, and my Phone (Verizon Rival). It's amazing how the same song on different equipment can sound so different when you have quality headphones.

I tried:
JVC HA-RX700 & HA-RX900
Sony V6, V600, V700, and other various headphones from them
Albet somethings... crap headphones...
Bose Over-Ear & Over-Ear w/Noise Canceling (lots of buzz on those)
Kilpsh iS4, S2 (IEM)
Shure 200's and another model
Skullcandy IEMs
Beats by Dre
Skullcandy Over-Ears (Skullcandy, DJs, and some others)

I also own Bose In-Ears (they are buds, though).

I listened to:
10 Years - Beautiful
3 Days Grace - Riot
Queen - Bohemian Rhapsody
Ludacris - couple songs
Akon - Mama Africa
Benny and the Band (Local Jazz)
Dave Mathews - Clips from a few songs

My final thoughts:
Skullcandy = Garbage for the price. Drop 'em down to a lower price bracket, and maybe
Bose = Not enough base with some songs or the trebles were too harsh
Bose w/NC = The constant buzz or hiss would drive me up a wall
JVCs = All of them were very good. Awesome for the price. Would disturb room mates though.
Sony = Same as above, richer bass and cleaner vocals (i.e. Queen)
Albets = Worse than skullcandy, but only $10-20 so to be expected
Skullcandy IEMs = Not bad really, but there was no bass or I couldn't get a seal
Shure IEMs = Freakin awesome-sauce, but a little uncomfy after 10 minutes.
Klipsh S2 = Same as above, but much more comfy. Not enough bass.
Klipsh S4 = Awesome aswell, comfy, and $60 cheaper than the Shure IEMs.

I finally chose the Klipsh S4 mainly because of how they sounded for movies and vocals. Bass is very good too. They felt a little more... powerful... for bass than the Shure's.

I know I said I wanted Over-the-Ear phones, but after some good points by Judge_Buff, I decided to give IEMs a shot. Glad I did cuz they sound amazing. By far the best sound I have ever heard from any sound source. Then again, I'm a bit sheltered to fancy audio stuff.

I am ever grateful.

Congrats. I am a s4 owner as well and you'll probably want to give them some burn in time between listens. Also they respond extremely well to EQ as I have changed my setting on vlc to get some more clarity out of them and a little less warm and they sound absolutely fantastic.

You've made a good choice, rapture! I hope you have much listening pleasure. I agree with jaysins about burn-in, too. Sorry about your wallet (LOL, I said it first.).

When you get in theater and start drawing that extra $$, start an Audio Kitty and get yourself some great gear. Every place I've ever been had audio and camera geeks that could show you ways to get gear out of Germany and Japan at less than retail. I hope that is still true in the 21st century.

Isn't it great rediscovering your music?