Welcome to the PSP family!! Yeap... you should check out the psp thread!! Here some quick answers.
Memory: PSP runs on a proprietary 333MHz processor and comes with 32MB of built-in memory, some of it reserved for the PSP's operating system and applications, and 4MB of embedded DRAM. (Cnet)
Theme: You can change the wallpaper through the "Photo" folder, select one the photo and hit the triangle button, there will be option for that.
Wi-fi: I have only used Starbuck, there's not much setting up needed for that, the steps are pretty self-explanatory and automatic once you are in the Network tab.
MP3: Yes
Video: I have tried PSP Video 9 before to convert video, pretty good for a free tools.

There are quite a few, I can't remember them now, you can try GameSpot PSP Videos.