

Personally, I'd go with Nintendo DS.
The PSP has a bit better graphics (about equal to a Playstation 2, though lower resolution). The Nintendo DS has TWO screens! And graphics better than an N64, but less than a GameCube (though it has Cell-shading and fog effects and other bits from the GC). Both have 802.11b built in, so you can play multiplayer wirelessly and connect to the internet (thats right, online Mario Kart!). Both have built in rechargeable battery.
The DS, though, with its two screens, has a touch screen for the first one, which introduces some cool gaming additions. The DS also is dual processor (an ARM7 from the GameBoy Advance and an ARM9).
The DS has dual slots, so you can play GameBoy Advance games AND DS games.
The PSP only plays PSP games on minidisks, and requires you to buy Sony memory sticks.
The DS also has a microphone built in.
I'd take the DS, since I like Nintendo games (zelda, mario, sonic, metroid prime: hunters) and think the dual screens and touch screen will make for some interesting games. That's just me personally.
If you could get either one for free, which would you choose?
http://www.nintendo.com/ds/overview.jsp
http://www.us.playstation.com/pressreleases.aspx?id=207
The DS is already working and playable, so you can watch some unbelievable videos of it.
Man, how could you forget to add a poll? - Phong