Welcome aboard, StickMang! Sorry about your wallet.
From my n00b perspective, getting a good pair of cans (like the ones you have already picked out) *and* a headphone amp is a great start. Where you start is entirely up to your budget, and how eager you are to jump in. The iPod has a surprisingly good analog out, so an amp is definitely not wasted on it.
You can get an amp for as little as $99 (the Total Airhead) and it will make a huge difference. If you can swing an extra $50, get the bithead instead, as you can use the USB to connect to your laptop, and it will sound much better than using the laptop's audio out. The bithead is what I started with, and it is still a valuable travelling companion.
The next big jump would be moving to a bigger amp, such as the micro line. The difference in sound quality between something like this and the bithead is not as huge as that between no amp and a bithead, but it is remarkable nonetheless. From there you can continue "down the irrevocable path to the Dark Side of audio bliss", and spend increasing amounts of money for the ever next level of audio refinement.
Your ears will never be the same again.
