I was just faced with the same decision, the 500 or the 2000. I ended up going with the 500 basically for 2 main reasons

-It was cheaper (now going for $150 at local Best Buys instead of the $199 from a few weeks ago)
-Had the hard buttons (this is a big deal because I didn't want to have to look at a screen to do some basic functions.)

IF the 3000 were out and it was the same price as the 2000 is now I would have absolutely gone with the 3000. The memory really isn't an issue for me with the 500. I knew it was a little harder to program because some codes are hard to learn but because codes from the 2000 could be converted to the 500 I figured I could eventually get everything I wanted in it.

I also figured that I would have a couple of good years of use with a relatively small investment then look for maybe a 3000 or use a PDA as a remote.