DS Ftw
I've owned both, and can happily say that both are incredible systems, but work for completely different gamer-styles.
The PSP, I found, is all about the flashier games that you can happily sit down and play for hours at a time. You have your movies, your homebrews, MP3's for when ye olde player is dead, and an interweb browser for when you're bored at work.
The DS, on the other hand, is a lot better for just popping open on a bus, train, or traffic light, and nipping quickly away at a puzzle or a quick level. The games tend to be a lot simpler, as we all know, but often put more focus into the gameplay and replayability... if it's even a word.