I discovered that the majority of the space, taken up by photo library is due to videos I have made with my iPhone and iPad. While I like preserving some of these video in original format for HQ viewing, I don't mind loosing some quality for others. Is there a quick way for doing so or do I need to import each separate video into a video-editing program and then export it again with the appropriate settings?
I would use Handbrake which is a free encode/recode program. You can batch files up, and choose various presets or your own choice of everything from resolution/bit rate/frames per second etc to decrease (you can never increase, obviously) the quality and therefore file sizes for your videos. My top tip would be to simply reduce resolution but keeping the smaller size dividable by the larger size, so if your videos are in iPhone 4 640x960 then try 320x480 for optimal conversion.
Many many other encoders are available, but most are paid solutions, and none are as fully featured in my opinion as Handbrake is. Speed depends on your CPU as it is all done in software, but recent versions of the software have included support for either Intel Quick Sync (If you have a Sandy Bridge or above Core iX CPU) and also OpenCL for using your GPU as extra processing resources - however I have never tested these, so I can't say how fast they may or may not be, or even if you have access to them.
Certainly for small phone videos even just using non hardware accelerated encoding you should see it take no more than 1/4 to 1/2 of the normal playtime of the file to convert, and likely a lot less than that.