Visor Deluxe of course.
Anyways, I would definitely recommend against any PDA if you plan on using it as a full laptop replacement (obviously). The PocketPC machines are nice and can do very well on their own, but if you ever plan on using real application software, you need a laptop. That may seem like a stupid comment, but you'd be amazed how little people know about these things. I personally believe the better buy in terms of support and full usability vs. cost is a Palm OS based system +/- a laptop (depending on one's needs). But then again, I'm biased. 🙂 For some people however, PocketPC does provide a reasonable in-between machine and is better for their needs.
I don't buy MP3 as a valid argument however. Same applies to MPEGs. The way I encode my MP3s, anything under 100 MB is virtually useless, since 100 MB would only hold about 20 songs for me. Plus, that's not even including space for application software. But again, that's just me, because many people ARE happy with 64 MB Rios.
Everything else you mentioned can be done on a Palm PDA, although the screen is smaller.
I would be interested in your experiences re: OS stability. I haven't used a PocketPC that much in all honesty since all of my friends now own a Palm OS PDA, so I don't know how stable it is. However, I do know that in comparison to Palm OS, the Windows CE machines crashed up the wazoo. (In fact, that's why many of my friends are now Palm and Visor owners. They used to own Windows CE machines. 😉) The Palm OS machines can also crash too, however, so on either platform you have to be careful not to install every crappy shareware program in existence.
NFS4, I know you weren't completely serious, but for everyone, just remember that an average PocketPC with a small (ie. not 1 Gig) IBM Microdrive is gonna cost $1000. 😛