I have a 60x 512MB SD card and a 150x 1GB SD card and even within the axim I can see a HUGE difference. Yes the time is greatly reduced with a USB 2.0 when putting a large file onto my 1 GB compared to my 512 MB, but it is not just then that I can tell the difference. When I am playing larger games I notice the faster loading times, and the smoother playing action of both games and video. I also agree with tallshorty about getting the 1 GB. If you are going to even think about watching a full length movie on your axim then you need at least a 1 GB, otherwise you either wont be able to fit the movie, or the quility will be so horrible you won't even want to watch it. Same goes for the mp3's if you have a 1 GB then you can at least have a variety of music, with a 512 MB if you listen to music very much at all you will get bored with it very quickly and have to reload it taking even more of your precious time. So go with at least a 1 GB and as high as speed as you are willing to pay for.
Something that is not coming out until sometime in the end of next year, but have a look at
http://www.pcworld.com/news/article/0,aid,122514,00.asp
Samsung is trying to introduce a SD card with 32 GB of memory! I can't imagine how much this will cost when it first comes out, but it will be absolutly awesome!