Another option would be to use an older sharp zaurus.  From what I know, these run linux as their OS.  I have a friend who has one and he uses it for mp3s, games, movie trailers, email, the works.  Oh, and it has all the normal PDA stuff on it as well.  =)  They were ~$500 used a year or so ago when I looked last, which does put a damper on the idea.