If you let your iPhone 4's Photos App Camera Roll get to past around 2000-3000 photos and videos, starting the Camera App gets very, very slow. Like 15-25 seconds, just to start it up. This is particularly noticeable if you get extremely low on iPhone storage space, when the warning pop-ups appear, telling you that you cannot record, due to low space.
I also noticed that manually killing recently-used-apps doesn't always help, nor does reboot, which folks discuss over here:
The only fix I've found is to get out Apple's white USB sync cable, and copy all the DCIM folders off the iPhone to a computer, then delete the iPhone's photos and movies within those folders.
Now you're all set, the Camera App is fast again right away, no reboot required. This tip likely also applies to the iPhone 4s and the iPhone 3GS. Let us know, with your comments below!