I started out with a PSP. At first it was great, such a novelty item with beautiful games that doubled as a music + movie player. It got old quick though. If you have an iPod, you won't use your psp as a music or movie player. The controls are awkward and the games (I don't know about the last year or so) are pretty awful.
I traded it in for a DS and have been enjoying it immensely. I actually got a DS just for the new zelda game coming out, but that has been delayed to hell. However the games I've picked up on the way aren't bad at all. The fact that you can play GBA games adds a bigger value. Add games such as castlevania, brain age, elite beat agents, etc etc and you're pretty much set.
Get the DS.