What kind of performance improvement should I expect on a Canon 500D with a class 6? Will a class 4 slow the writes/reads noticeably? I mostly take (low shutter speed) photos and occasional short videos.
Class 4 is 32MBit/s (4MByte/s) and Class 6 is 48MBit/s (6MByte/s). You probably shouldn't worry about this if you're just shooting JPEGs, but if you're going to take RAW shots in quick succession, or, as you said, take video, it may make a difference. I can't speak for all camera manufacturers, but if the write speed isn't high enough on the card, you may not be able to take the highest quality video your camera can offer.
So I would personally recommend you get the Class 6 SDHC card. You'll be able to shoot pictures faster, and you won't limit yourself in terms of video. In short, "better safe than sorry".
Cards of a particular class are not all made the same. Hence the preferred cards are the more expensive because they produce the best results in terms of speed and reliability.
Look at the sandisk models. They are very popular with professionals for the reasons mentioned above. Personally I took a chance on the Transcend model to get more bang for my bucks. It provides 16 Gigs on a class 10 card and have no problems to report with it after almost a year of usage.
I have a Canon 500D and own a few Sandisk Extreme III's which are extremely fast and I'd generally recommend them... but essentially they outperform the camera.
Most of the time I use a couple of PNY 16gb Class 4's simply because of the convenient size when taken RAW's. The only slowdown I ever notice is that which is from the camera's buffer size and write speeds itself that is documented in the many reviews/specs rather than from the card itself. I've never had any slowdown issues from pictures or video on the camera from the card, but there may well be not so good quality Class 4's out there that will effect the use of the camera
The Sports Photo Guy regularly reviews different SD (and CF) cards and posts the real world results. I'd highly recommend reading his reviews since you'll find that there are some class 4 cards that are faster than supposed class 6 cards.