GD is easier to set up, as it comes bundled with PHP, wheras ImageMagick needs to be set up. If you both have them up-and-running, then go for ImageMagick, as it has a sightly better performance and support for more image formats.
Main difference between the two is the way batch-add is being done: when using GD, one pic after the other is processed, which is good in terms of server load. Drawback is that you might have issues resizing larger pics (both in terms of dimensions and filesize), as you're limited by the memory assigned to PHP. ImageMagick on the other hand is quite resources-hungry, and it will start a separate process for each pic that needs to be resized during batch-add, which can bring the server down.
Bottom line: both have advantages and disadvantages. Your choice. If the server is yours to administer and you know what you're doing, go for ImageMagick. Won't hurt to test both, you can change the library at any time (Coppermine's config => method for resizing pics).
However, you shouldn't set up cpg1.3.x when starting from scratch, but use the most recent version (currently cpg1.4.8).