There are a couple of routes you could take....dynamic or electrostatic phones.....at around £500 all in,you could get to the lower end of the Stax range for electrostatic phones,and I'm sure that someone will give you a good rundown on those.
My own preference is for dynamic phones,and the Sennheiser 600/650's should be in your range....both are excellent,with a very nice overall sound balance,and easy on the head as well.
You could also look at Beyer and Grado,both having a good range for you to look at.
I wouldn't go for the lead upgrades immediately....use the phones for a while if you do buy the Sennheisers,and take your time over choices....if you buy these,or any other good set of dynamic phones,you will need a headphone amp.
At up to £300,there is quite a range,from MF XCans,and Creeks,through to used Earmaxs,and Slee amps,plus all of the others you'll find here.
It would be worth your while having a look at the following also:
www.ipodstudio.com www.head-fi.org