+1 AMW1011 for a good pair of cans and a clip on mic..
Personally, I would recommend a pair of
Grado i60's and a
Clip-On Microphone.
Total cost will be around $89 and the Grado i60's are a great sounding pair of cans that are easy to drive (no amplifier necessary).
I have a pair of Grado i60's with bowls as my walk-around cans and can attest that they sound nearly as good as my at home AKG K701's.
Great sound stage, detailed mids to lows and high ends that is nary a touch shy of the AKG's (and would probably be closer if I used them with the Essence STX instead of an iPod Touch :/).
I have also heard good things regarding the AD700's but have unfortunately not heard them myself.
Judging from
HeadRoom's frequency graphs however, I would expect a cooler sound (not as much, but somewhat more accurate, bass), quite recessed upper mids and a sound that is not quite as smooth.
Although I prefer the Grado's, both pairs of headphones would be a definite improvement over what you have and what has been recommended so far.
Beyond the cans, if you are planning on picking up a new sound card (as the Megalodons are USB headphones) I would recommend either the
ASUS Xonar D1 (PCI) or
Xonar Dx (PCIe).
Both are identical aside from the interface and offer excellent sound quality.
The also offer Dolby Headphone so you can continue to game and watch movies in virtual surround sound.